Rotate a Singly Linked List

Rotate a Singly Linked List

This article will explain how we can rotate the singly linked list. Here we have given a singly linked list, and we need to rotate this list by k nodes anti-clockwise where k is a positive number.

Example:

        List is: 2 -> 4 -> 6 -> 8 -> 10 -> 12                       k: 4

        Output: 10 -> 12 -> 2 -> 4 -> 6 -> 8

NOTE: Assume that k is smaller than the length of the linked list.

Method-1:

For rotating the linked list, we need to change the next of the kth node to the NULL. We will change the next of the last node to the previous head node, and then we need to change the head to (k+1)th node.

We will traverse the list from the starting to the kth node. We need to store the pointer to the kth node. We can get (k+1)th node using kthNode  ->  next. We will keep traversing till the end and store the pointer to the last node also. Finally, we will change pointers as we discussed above.

C program to rotate a linked list anti-clockwise by Method-1

 #include<stdio.h>
 #include<stdlib.h>
 struct node
 {
 int info;
 struct node * next;
 };
 struct node * start = NULL;
 // For inserting the elements in the linked list
 void add(int item)
 {
 struct node * t, * p;
 t = (struct node *)malloc( sizeof( struct node ));
 if(start == NULL)
 {
 start = t;
 start -> info = item;
 start -> next = NULL;
 return;
 }
 else
 {
 struct node * p = start;
 while(p -> next != NULL)
 {
 p = p -> next;
 }
 p -> next = t;
 p = p -> next;
 p -> info = item;
 p -> next = NULL;
 }
 }
 // Function for rotating the linked list
 void rotate(struct node * head, int k)
 {
     if (k == 0)
         return;
     struct node* curr = head;
     int count = 1;
     while (count < k && curr != NULL) {
         curr = curr -> next;
         count++;
     }
     if (curr == NULL)
         return;
     struct node* temp = curr;
     while (curr -> next != NULL)
         curr = curr -> next;
     curr -> next = head;
     head = temp -> next;
     temp -> next = NULL;
     start = head;
 }
 // To display the elements of the linked list
 void traverse(struct node * t)
 {
 if(t == NULL)
 {
             printf(" Linked list is empty\n");
                                     }
                                     while(t -> next != NULL)
                                     {
                         printf("%d ->  ",t -> info);
                         t = t -> next;
                         }
                         printf("%d\n",t -> info);
 }
 // Driver Function
 int main()
 {
     int k;
     printf("Enter the value of k:");
     scanf("%d",&k);
     add(2);
     add(4);
     add(6);
     add(8);
     add(10);
     add(12);
     add(14);
     add(16);
     printf("Given Linked List: \n");
     traverse(start);
     rotate(start,k);
     printf("Linked List after rotating: \n");
     traverse(start);
     return 0;
 } 

Output:

Time Complexity: The time complexity of this method is O(n), where n is the total number of the nodes in the linked list.

Method-2:

In this method, we will first make the linked list circular and then move k-1 steps ahead form the starting or the head node. We will make it null and make the kth node as head of the linked list.

C program to rotate a linked list anti-clockwise by Method-2

 #include<stdio.h>
 #include<stdlib.h>
 struct node
 {
 int info;
 struct node * next;
 };
 struct node * start = NULL;
 // For inserting the elements in the linked list
 void add(int item)
 {
 struct node * t, * p;
 t = (struct node *)malloc( sizeof( struct node ));
 if(start == NULL)
 {
 start = t;
 start -> info = item;
 start -> next = NULL;
 return;
 }
 else
 {
 struct node * p = start;
 while(p -> next != NULL)
 {
 p = p -> next;
 }
 p -> next = t;
 p = p -> next;
 p -> info = item;
 p -> next = NULL;
 }
 }
 // Function for rotating the linked list
 void rotate(struct node * head, int k)
 {
     int i;
     if (k == 0)
         return;
    struct node * curr = head;
 // For making the linked list circular
    while(curr -> next != NULL)
    {
             curr = curr -> next;
    }
    curr -> next = head;
    curr = head;
    for(i=1; i < k ; i++)
    {
             curr = curr -> next;
    }
    head = curr -> next;
    curr -> next = NULL;
    start = head;
 }
 // To display the elements of the linked list
 void traverse(struct node * t)
 {
 if(t == NULL)
 {
             printf(" Linked list is empty\n");
                                     }
                                     while(t -> next != NULL)
                                     {
                         printf("%d ->  ",t -> info);
                         t = t -> next;
                         }
                         printf("%d\n",t -> info);
 }
 // Driver Function
 int main()
 {
     int k;
     printf("Enter the value of k:");
     scanf("%d",&k);
     add(2);
     add(4);
     add(6);
     add(8);
     add(10);
     add(12);
     add(14);
     add(16);
     printf("Given Linked List: \n");
     traverse(start);
     rotate(start,k);
     printf("Linked List after rotating: \n");
     traverse(start);
     return 0;
 } 

Output: -

Time Complexity: The time complexity of this method is O(n), where n is the total number of the nodes in the linked list.