Home » Interview Questions » LinkedList Interview Questions » Rotate a Linked List

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

READ  Merge Two Sorted Linked Lists

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions