September 30, 2024

Rotate A Linked List

Problem Statement

You are given the head of a singly linked list and an integer K, write a program to Rotate the Linked List in a clockwise direction by K positions from the last node.

Example

Input-1

Head:  10->20->30->40->50 
K: 2

Output-1

40->50->10->20->30

Explanation

Here, we have rotated the linked list exactly 2 times. On the First rotation 5 becomes head and 4 becomes tail, and on the second rotation 4 becomes head and 3 becomes the tail node.

Input-2

Head:  10->20->30 
K: 4

Output-2

30->10->20

Explanation

Here, we have rotated the linked list exactly 4 times. As you can see below.

Constraints

The number of nodes in the linked list is in the range [1 to 500].
-100 <= Node.val <= 100
0 <= k <= 2 * 10^9

Algorithm 1 – Just by Changing the Next Pointer for Any kth Node

Intuition:

In this approach, we need to maintain three-pointers to (k+1)^th^ node, kth node, and the previous node. The idea here is to traverse through the linked list until the kth node, then change the k+1^th^ node to NULL and the next pointer of the last node should point to the current head node after that make the k+1^th^ node a new head of the linked list.

Algorithm

Check whether the head is null or k == 0. If so, return.
Initialize a variable that will store the number of nodes in the linked list and set the variable count to 1 (for head).
Traverse through the linked list until the kth node.
If the current is NULL or k^th^ node is greater than or equal to the number of nodes in a linked list. Don’t change the list in this case, Hence return.
Now traverse through all the nodes linked list till the end and change next pointer of the last node to previous head.
Finally the change head to k+1^th^ node and then change the k+1^th^ node to NULL.

Code Implementation

Code in C++

// rotate a linked list
#include<bits/stdc++.h>
using namespace std;

class node {
    public:
        int num;
        node* next;
        node(int a) {
            num = a;
            next = NULL;
        }
};
//utility function to insert node at the end of the list
void insertNode(node* &head,int val) {
    node* newNode = new node(val);
    if(head == NULL) {
        head = newNode;
        return;
    }
    node* temp = head;
    while(temp->next != NULL) temp = temp->next;
    
    temp->next = newNode;
    return;
}
//utility function to rotate list by k times
node* rotateRight(node* head,int k) {
    if(head == NULL||head->next == NULL) return head;
    for(int i=0;i<k;i++) {
        node* temp = head;
        while(temp->next->next != NULL) temp = temp->next;
        node* end = temp->next;
        temp->next = NULL;
        end->next = head;
        head = end;
    }
    return head;
}
//utility function to print list
void printList(node* head) {
    while(head->next != NULL) {
        cout<<head->num<<"->";
        head = head->next;
    } 
    cout<<head->num<<endl;
    return;
}

int main() {
    node* head = NULL;
    //inserting Node
    insertNode(head,1);
    insertNode(head,2);
    insertNode(head,3);
    insertNode(head,4);
    insertNode(head,5);
    
    cout<<"Original list: ";
    printList(head);
    
    int k = 2;
    node* newHead = rotateRight(head,k);//calling function for rotating right of 
    //the nodes by k times
    
    cout<<"After "<<k<<" rotations: ";
    printList(newHead);//list after rotating nodes
    return 0;
}

Code in Java

// rotate a linked list
import java.util.*;
class Node {
  int num;
  Node next;
  Node(int a) {
    num = a;
    next = null;
  }
}
class Main {
  //utility function to insert node at the end of the list
  static Node insertNode(Node head, int val) {
    Node newNode = new Node(val);
    if (head == null) {
      head = newNode;
      return head;
    }
    Node temp = head;
    while (temp.next != null) temp = temp.next;

    temp.next = newNode;
    return head;
  }
  //utility function to rotate list by k times
  static Node rotateRight(Node head, int k) {
    if (head == null || head.next == null) return head;
    for (int i = 0; i < k; i++) {
      Node temp = head;
      while (temp.next.next != null) temp = temp.next;
      Node end = temp.next;
      temp.next = null;
      end.next = head;
      head = end;
    }
    return head;
  }
  //utility function to print list
  static void printList(Node head) {
    while (head.next != null) {
      System.out.print(head.num + "->");
      head = head.next;
    }
    System.out.println(head.num);

  }

  public static void main(String args[]) {
    Node head = null;
    //inserting Node
    head = insertNode(head, 1);
    head = insertNode(head, 2);
    head = insertNode(head, 3);
    head = insertNode(head, 4);
    head = insertNode(head, 5);

    System.out.print("Original list: ");
    printList(head);

    int k = 2;
    Node newHead = rotateRight(head, k); 
    //calling function for rotating right of the nodes by k times

    System.out.print("After " + k + " rotations: ");
    printList(newHead); //list after rotating nodes

  }
}

Code in Python

# rotate a linked list
# Python program to rotate a linked list

# Node class
class Node:

	# Constructor to initialize the node object
	def __init__(self, data):
		self.data = data
		self.next = None

class LinkedList:

	# Function to initialize head
	def __init__(self):
		self.head = None

	# Utility function to print it the linked LinkedList
	def printList(self):
		temp = self.head
		while(temp):
			print(temp.data)
			temp = temp.next
			
	
    # Function to insert a new node at the beginning
	def push(self, new_data):
		# allocate node and put the data
		new_node = Node(new_data)

		# Make next of new node as head
		new_node.next = self.head
		
		# move the head to point to the new Node
		self.head = new_node


	def rotate(self, k):
		if k == 0:
			return
		
		current = self.head
		
		# current will either point to kth or NULL after
		# this loop
		# current will point to node 40 in the above example
		count = 1
		while(count <k and current is not None):
			current = current.next
			count += 1
	
		# If current is None return
		if current is None:
			return

		# current points to kth node. Store it in a variable
		kthNode = current
	
		# current will point to last node after this loop
		while(current.next is not None):
			current = current.next

		# Change next of last node to previous head
		current.next = self.head
		
		# Change head to (k + 1)th node
		self.head = kthNode.next

		# change next of kth node to NULL
		kthNode.next = None



# Driver program to test above function
llist = LinkedList()

llist.push(5)
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)

print("Original linked list")
llist.printList()
llist.rotate(2)

print("\nRotated Linked list")
llist.printList()

Output

Original list: 1->2->3->4->5
After 2 rotations: 4->5->1->2->3

Time Complexity

The time complexity is O(n). Since we traversed the linked list only once to rotate a linked list, where n is the size of the linked list.

Space Complexity

The space complexity is O(1). Since no extra space is used in the Program to rotate a linked list.

Algorithm 2 – By Rotating K Nodes

Intuition:

The idea here is is similar to the previous one the only difference is to first convert the singly linked list to a circular linked list and then move k-1 steps forward from the head node but before moving, make the k-1^th^ node next to null and next node as head.

Algorithm

Check whether the head is null or k == 0. If so, return.
Initialize a variable length that will store the number of nodes in the linked list and set the variable count to 1 (for head).
Link the last node to the head by pointing next to the last node to the head as it will convert the singly linked list to a circular list.
Traverse the linked list to k-1^th position which will be last element.
Iterate over the last node and break the linked list by pointing the last node to null.

Code Implementation

Code in C++

// rotate a linked list
#include<bits/stdc++.h>
using namespace std;

class node {
    public:
        int num;
        node* next;
        node(int a) {
            num = a;
            next = NULL;
        }
};

// function for adding nodes in a linked list
void insertNode(node* &head,int val) {
    node* newNode = new node(val);
    if(head == NULL) {
        head = newNode;
        return;
    }
    node* temp = head;
    while(temp->next != NULL) temp = temp->next;
    
    temp->next = newNode;
    return;
}
//utility function to rotate list by k times
node* rotateRight(node* head,int k) {
    if(head == NULL||head->next == NULL||k == 0) return head;
    //calculating length
    node* temp = head;
    int length = 1;
    while(temp->next != NULL) {
        ++length;
        temp = temp->next;
    }
    //link last node to first node
    temp->next = head;
    k = k%length; //when k is more than length of list
    int end = length-k; //to get end of the list
    while(end--) temp = temp->next;
    //breaking last node link and pointing to NULL
    head = temp->next;
    temp->next = NULL;
        
    return head;
}

//utility function to print list
void printList(node* head) {
    while(head->next != NULL) {
        cout<<head->num<<"->";
        head = head->next;
    } 
    cout<<head->num<<endl;
    return;
}

int main() {
    node* head = NULL;
    //inserting Node
    insertNode(head,1);
    insertNode(head,2);
    insertNode(head,3);
    insertNode(head,4);
    insertNode(head,5);
    
    cout<<"Original list: ";
    printList(head);
    
    int k = 2;
    node* newHead = rotateRight(head,k);//calling function for rotating right of the nodes by k times
    
    cout<<"After "<<k<<" rotations: ";
    printList(newHead);//list after rotating nodes
    return 0;
}

Code in Java

// rotate a linked list
import java.util.*;
class Node {
        int num;
        Node next;
        Node(int a) {
            num = a;
            next = null;
        }
}
class Main {
static Node insertNode(Node head,int val) {
    Node newNode = new Node(val);
    if(head == null) {
        head = newNode;
        return head;
    }
    Node temp = head;
    while(temp.next != null) temp = temp.next;
    
    temp.next = newNode;
    return head;
}

//utility function to print list
static void printList(Node head) {
    while(head.next != null) {
        System.out.print(head.num+"->");
        head = head.next;
    } 
    System.out.println(head.num);
    
}

//utility function to rotate list by k times
static Node rotateRight(Node head,int k) {
    if(head == null||head.next == null||k == 0) return head;
    //calculating length
    Node temp = head;
    int length = 1;
    while(temp.next != null) {
        ++length;
        temp = temp.next;
    }
    //link last node to first node
    temp.next = head;
    k = k%length; //when k is more than length of list
    int end = length-k; //to get end of the list
    while(end--!=0) temp = temp.next;
    //breaking last node link and pointing to NULL
    head = temp.next;
    temp.next = null;
        
    return head;
}


public static void main(String args[]) {
    Node head = null;
    //inserting Node
    head=insertNode(head,1);
    head=insertNode(head,2);
    head=insertNode(head,3);
    head=insertNode(head,4);
    head=insertNode(head,5);
    
    System.out.println("Original list: ");
    printList(head);
    
    int k = 2;
    Node newHead = rotateRight(head,k);
    //calling function for rotating right of the nodes by k times
    
    System.out.println("After "+k+" rotations: ");
    printList(newHead);//list after rotating nodes

}
}

Code in Python

# rotate a linked list
class Node:
      
    def __init__(self):
          
        self.data = 0
        self.next = None
  
# utility function to rotate list by k times
def rotate(head_ref, k):
  
    if (k == 0):
        return
   
    current = head_ref
   
    # Traverse till the end.
    while (current.next != None):
        current = current.next
   
    current.next = head_ref
    current = head_ref
      
    # Traverse the linked list to k-1 
    # position which will be last element
    # for rotated array.
    for i in range(k - 1):
        current = current.next
   
    # Update the head_ref and last 
    # element pointer to None
    head_ref = current.next
    current.next = None
    return head_ref
   

# Function to push a node 
def push(head_ref, new_data):
  
    new_node = Node()
   
    # Put in the data 
    new_node.data = new_data
   
    # Link the old list off 
    # the new node 
    new_node.next = (head_ref)
   
    (head_ref) = new_node
    return head_ref
      
# Function to print linked list 
def printList(node):
  
    while (node != None):
        print(node.data, end = ' ')
        node = node.next
  
# Main code
if __name__=='__main__':
      
    head = None
   
    for i in range(5, 0, -1):
        head = push(head, i)
   
    print("Original List")
    printList(head)
    head = rotate(head, 4)
   
    print("\nAfter 2 rotations:")
    printList(head)

Output

Original list: 1->2->3->4->5
After 2 rotations: 4->5->1->2->3

Time Complexity

The time complexity is O(n). Since we traversed the linked list only once to rotate a linked list, where n is the size of the linked list.

Space Complexity

The space complexity is O(1). Since no extra space is used in the Program to rotate a linked list.

Conclusion

We have given the head of a singly linked list and an integer K. We had to write a program to Rotate the Linked List by K nodes in a clockwise direction from the last node.
For eg, A head of the linked list is given as Head: 1->2->3->4->5 and an integer K = 2, here the output should be 4->5->1->2->3 after two rotations.
We have learned two approches to rotate a linked list, first is by changing the next pointer for any k^th node and the second approach we saw is by rotating K nodes.
The both algorithms takes O(n) time complexity as we traversed the linked list only once, and O(1) space complexity because no extra space is used.
We can simply convert a singly linked list to a circular linked list just by pointing last node next to the head of the linked list.

FAQ

Q:What does it mean to rotate a linked list?

A: It means the node is moved clockwise or counterclockwise depending on the situation by treating the linked list as a circular structure.

Q:How to rotate a linked list?

A rotate a linked list, move the nodes in either a clockwise or counterclockwise direction. You can do this by moving the nodes from the front to the back of the linked list or vice versa.

Q:Can a singly linked list be a circular linked list?

A: Yes, A singly linked list can be a circular linked list, when the last node point to the first node rather than pointing to the NULL.

Q:How to convert a singly linked list to a circular linked list?

A: We can simply convert a list to a circular linked list just by pointing the last node next to the head of the linked list.

Q:What are some similar coding questions on Linked List?

A: Refer Detect Loop in Linked List
Refer Reverse alternate K nodes in a Singly Linked List
Refer Reverse a Linked List

Author

Vishwas Sharma

View all posts

Rotate A Linked List

Problem Statement

Example

Input-1

Output-1

Explanation

Input-2

Output-2

Explanation

Constraints

Algorithm 1 – Just by Changing the Next Pointer for Any kth Node

Intuition:

Algorithm

Code Implementation

Output

Time Complexity

Space Complexity

Algorithm 2 – By Rotating K Nodes

Intuition:

Algorithm

Code Implementation

Output

Time Complexity

Space Complexity

Conclusion

FAQ

Author

Latest articles

Largest Number Formed from an Array

Fundamentals of Enhanced Interior Gateway Routing Protocol

What is Network Hub?

Largest Number Formed from an Array

Fundamentals of Enhanced Interior Gateway Routing Protocol

What is Network Hub?

Rotate A Linked List

Problem Statement

Example

Input-1

Output-1

Explanation

Input-2

Output-2

Explanation

Constraints

Algorithm 1 – Just by Changing the Next Pointer for Any kth Node

Intuition:

Algorithm

Code Implementation

Output

Time Complexity

Space Complexity

Algorithm 2 – By Rotating K Nodes

Intuition:

Algorithm

Code Implementation

Output

Time Complexity

Space Complexity

Conclusion

FAQ

Author

Latest articles

Largest Number Formed from an Array

Fundamentals of Enhanced Interior Gateway Routing Protocol

What is Network Hub?

Featured articles

Largest Number Formed from an Array

Fundamentals of Enhanced Interior Gateway Routing Protocol

What is Network Hub?