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

5. Return the new head

C++ Program

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

struct LLNode{
	int data;
	LLNode *next;	
};
void display(LLNode**head);

LLNode* revAlternateKNodes(LLNode* head, int k)
{
  LLNode* temp = head;
  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//
  if(head != NULL)
    head->next = temp; 
   

  //  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;

}
 

void insertAtBeginning(LLNode**head,int dataToBeInserted)
{
	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
			*head=curr;
		
	else //make the next of the current node point to the present head and make the current node as the new head
		{
			curr->next=*head;
			*head=curr;
		}
		
		//O(1) constant time
}


void display(LLNode**head)
{
	LLNode*temp=*head;
	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;
	insertAtBeginning(&head,6);
	insertAtBeginning(&head,16);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,50);
	insertAtBeginning(&head,1);
	insertAtBeginning(&head,23);


	
	cout<<"\nCurrent List is :-\n";
	display(&head);
	head = revAlternateKNodes(head,k);
	cout<<"After reversing alternate k nodes"<<endl;
	display(&head);
	return 0;
}
Try It

 


Next > < Prev
Scroll to Top