Rotate a Linked List

Given a linkedlist and an integer k, write a function to rotate the linked list counter clockwise by k nodes.

Example

Current List is :-
23 ->1 ->50 ->15 ->16 ->6
K = 4

After rotating the linked list counter clockwise by k nodes
16 ->6 ->23 ->1 ->50 ->15

In the above example you can see that the list is rotated counter clockwise by 4 nodes. Consider 16, it is moved left(ie counter clockwise) by 4 nodes. Simlarly to other elements.

Time Complexity : O(n)

Algorithm

1. Traverse the first k nodes, and store pointer to the Kth node. ie, temp

2. Store the Kth node in a KthNode pointer ie, KthNode = temp

3. Move temp to the last node

4. Change next of last node to head ie, temp->next = head

5. Change head to the next of KthNode ie, head = KthNode->next

6. Point next of KthNode to NULL ie, KthNode->next = NULL

The above algorithm can be clearly explained in below diagram

C++ Program

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

struct LLNode{
	int data;
	LLNode *next;	
};
//This funnction will rotate the list counter clockwise by k nodes
void rotate(LLNode** head, int k)
{
  LLNode* temp = *head;
  int count = 1;
  if (k==0)
  {
    return ;
  }
  //Pointing temp to the kth node
  while(count<k && temp != NULL) {
      temp = temp->next;
      count++;
  }
  //If it is NULL then dont rotate
  if (temp==NULL)
  {
    return;
  }
  //point KthNode to temp
  LLNode* KthNode = temp;
  //Move temp to the last node
  while(temp->next != NULL) {
      temp = temp->next;
  }
  //point next of temp to the head
  temp->next = *head;
  //change head to the next of Kth node
  *head = KthNode->next;
  //Point next of KthNode to NULL
  KthNode->next = NULL;
}
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 = 4;

	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);
	rotate(&head, k);
	cout<<"After rotating the linked list counter clockwise by k nodes"<<endl;
	display(&head);
	return 0;
}

 

Translate ยป