Rotate A Linked List
FREE
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
Transform Your Career
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
Output-1
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
Output-2
Explanation
Here, we have rotated the linked list exactly 4 times. As you can see below.
Constraints
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.
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ moreCode Implementation
Code in C++
Code in Java
Code in Python
Output
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
Turn Learning into Career Growth
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++
Code in Java
Code in Python
Output
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
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