# Reverse alternate k nodes in a Singly Linked List

## Given a linked list and a value k, write a function that will reverse every alternate k nodes.

### Example

INPUT
1->2->3->4->5->6
k = 2

OUTPUT
2->1->3->4->6->5

In the above example we can see that every atlernate two nodes are reversed ie, 1->2 reversed to 2->1 and 3->4 is not reversed and again 5->6 got reversed to 6->5.

Time Complexity: O(n)

## Algorithm

1. Reverse first k nodes and make temp point to the (k+1)th node

2. Now, point head to the kth node ie, change next of head to (k+1)th node.

3. Traverse next k nodes that are to be skipped ie, move temp pointer

4. recursively call steps 1-3

## C++ Program

#include <bits/stdc++.h>
using namespace std;

struct LLNode{
int data;
LLNode *next;
};

{
LLNode* next;
LLNode* prev = NULL;
int count = 0;

// reverse first k nodes of the linked list //
while (temp != NULL && count < k)
{
next  = temp->next;
temp->next = prev;
prev = temp;
temp = next;
count++;
}
// Now head points to the kth node ie, change next of head to (k+1)th node//

//  move the temp pointer to skip next k nodes //
count = 0;
while(count < k-1 && temp != NULL )
{
temp = temp->next;
count++;
}
//cout<<temp->data<<endl;
// Recursively call for the list starting from temp->next.
// And make rest of the list as next of first node //
if(temp !=  NULL)
temp->next = revAlternateKNodes(temp->next, k);

// prev is new head of the input list //
return prev;

}

{
LLNode*curr=new LLNode;
//make a new node with this data and next pointing to NULL
curr->data=dataToBeInserted;
curr->next=NULL;

if(*head==NULL) //if list is empty then set the current formed node as head of list

else //make the next of the current node point to the present head and make the current node as the new head
{
}

//O(1) constant time
}

{
while(temp!=NULL) //till the list ends (NULL marks ending of list)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

int main()
{

LLNode *head = NULL; //initial list has no elements
int k = 2;

cout<<"\nCurrent List is :-\n";