Introduction
This blog will discuss the various approaches to solve the Reverse alternate K nodes in a Singly linked list problem. Before jumping into the problem of getting the Reverse alternate K nodes in a Singly Linked List, let’s first understand a Linked list.
A Linked list is a kind of data structure in which the elements are connected using pointers, and each node has the address of the pointer of its next node.
In this Reverse alternate K nodes in a Singly Linked List problem, we need to return the head of the linked list after reversing all the alternate k nodes.
You can refer to this link for more information on the linked list.
For Example:-
List :- 10 -> 15 -> 45 -> 17 -> 145 -> 125 -> 5 -> 11 -> 47 -> 43 -> 1 -> 75 , and K = 3
Output :- 45 -> 15 -> 10 -> 17 -> 145 -> 125 -> 47 -> 11 -> 5 -> 43 -> 1 -> 75
Recommended Topic, Floyds Algorithm
Brute Force Approach
Brute Force Solution considers reversing the first ‘K’ nodes and iterating the pointer ‘K’ indexes forward, and then making a recursive call to reverse the next ‘K’ nodes. In this approach, the recursive call will be decided using a boolean variable.
Algorithm
Step 1. Create a function ‘getResult()’ that will accept three parameters, i.e., one head pointer of the linked list, one variable ‘K’, and one boolean variable ‘x’, initially ‘x’ is true.
Step 2. Check if ‘X’ is true, then we have to reverse the first ‘K’ nodes by calling the recursive function ‘getResult()’.
Step 3. Check if ‘X’ is false, then we have to iterate our pointer and jump to the node at a distance ‘K’ from that node.
Step 4. We need to call the recursive function ‘getResult()’ and repeat the process for the remaining nodes and link the resultant list with the tail of the first ‘K’ nodes modified initially.
Step 5. Return the ‘head’ of the resultant modified, linked list.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node *next;
Node(int data)
{
this->data = data;
this->next = NULL;
}
};
Node *takeinput()
{
int data;
cin >> data;
Node *head = NULL, *tail = NULL;
while (data != -1)
{
Node *newNode = new Node(data);
if (head == NULL)
{
head = newNode;
tail = newNode;
}
else
{
tail->next = newNode;
tail = newNode;
}
cin >> data;
}
return head;
}
/* Function to print the linked list */
void print(Node *head)
{
Node *temp = head;
while (temp != NULL)
{
cout << temp -> data << " ";
temp = temp -> next;
}
return;
}
Node *getResult(Node *node, int k, bool x)
{
if (node == NULL)
{
return NULL;
}
int count = 1;
Node *prev = NULL;
Node *temp = node;
Node *next = NULL;
while (temp != NULL && count <= k)
{
next = temp -> next;
/* Reverse the nodes only if x is true*/
if (x == true)
{
temp -> next = prev;
}
prev = temp;
temp = next;
count++;
}
if (x == true)
{
node -> next = getResult(temp, k, !x);
return prev;
}
prev -> next = getResult(temp, k, !x);
return node;
}
Node *reverse(Node *head, int k)
{
return getResult(head, k, true);
}
int main()
{
Node *head = takeinput();
cout << "Given Linked List:- " ;
print(head);
cout << endl;
int k = 3;
head = reverse(head, k);
cout << "Modified Linked List:- " ;
print(head);
}
Output :
Given Linked List:- 10 -> 15 -> 45 -> 17 -> 145 -> 125 -> 5 -> 11 -> 47 -> 43 -> 1 -> 75
Modified Linked List:- 45 -> 15 -> 10 -> 17 -> 145 -> 125 -> 47 -> 11 ->Complexity Analysis
Time Complexity: O(N)
Incall to ‘getResult()’, we are working on ‘K’ nodes at one time, either it is the job of reversing the nodes or just traversing them, and in total, we are working on ‘’ nodes, therefore, the overall time complexity is O(N).
Space Complexity: O(N)
As we are using a linked list of size ‘N’, therefore, the overall space complexity will be O(N).
19+ registered 
