Rotate List — Solution in Python, Java & C++
Rotate List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on two pointers.
Rotate List is a medium coding problem on two pointers, asked in Amazon, Microsoft, Bloomberg and LinkedIn interviews.
- Difficulty: Medium
- Topics: Two Pointers
- Asked at: Amazon, Microsoft, Bloomberg, LinkedIn
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the head of a singly linked list, rotate the list to the right by k places: k times, the last node moves to the front. Return the head of the rotated list.
Example 1
Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
Explanation: One rotation gives [5,1,2,3,4], a second gives [4,5,1,2,3].
Example 2
Input: head = [0,1,2], k = 4
Output: [2,0,1]
Explanation: Rotating a 3-node list 3 times brings it back, so 4 rotations equal 1.
Example 3
Input: head = [], k = 7
Output: []
Constraints
The number of nodes in the list is in the range [0, 500]-100 <= Node.val <= 1000 <= k <= 2 * 10^9
Hints for Rotate List
Hint 1
Rotating a list of length
nbynchanges nothing, so onlyk % nmatters —kcan be two billion.Hint 2
After rotating by
s = k % n, the lastsnodes come first. The new tail is the node at positionn - s(1-based).Hint 3
Find the length and the old tail in one walk, link the tail to the head to form a ring, walk to the new tail, and cut the ring after it.
How to solve Rotate List
A right rotation by s moves the last s nodes to the front. Closing the list into a ring and cutting it at the right place does that with two pointer changes.
Approach
- If the list is empty, return it.
- Walk to the last node, counting the length
n. - Set
s = k % n; ifs == 0returnhead. - Link the tail to
head, then walkn - ssteps from the tail (orn - s - 1from the head) to the new tail. - The node after it is the new head; set the new tail's
nextto null and return the new head.
Why it works
In the ring every node keeps its successor, so the order is unchanged up to where we cut; cutting after position n - s makes position n - s + 1 the first node, which is exactly the list rotated right by s.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Simulating
ksingle rotations is far too slow forkup to 2·10^9 — reducekmodulo the length first. - Guard the empty list before taking
k % n(division by zero). - When
k % n == 0return the list unchanged rather than cutting the ring in the wrong place.
Reference solution
Python
from typing import Optional
def rotateRight(head: Optional[ListNode], k: int) -> Optional[ListNode]:
if head is None:
return head
n = 1
tail = head
while tail.next:
tail = tail.next
n += 1
s = k % n
if s == 0:
return head
tail.next = head
new_tail = head
for _ in range(n - s - 1):
new_tail = new_tail.next
new_head = new_tail.next
new_tail.next = None
return new_headJava
public static ListNode rotateRight(ListNode head, int k) {
if (head == null) return head;
int n = 1;
ListNode tail = head;
while (tail.next != null) { tail = tail.next; n++; }
int s = k % n;
if (s == 0) return head;
tail.next = head;
ListNode newTail = head;
for (int i = 0; i < n - s - 1; i++) newTail = newTail.next;
ListNode newHead = newTail.next;
newTail.next = null;
return newHead;
}C++
ListNode* rotateRight(ListNode* head, int k) {
if (!head) return head;
int n = 1;
ListNode* tail = head;
while (tail->next) { tail = tail->next; n++; }
int s = k % n;
if (s == 0) return head;
tail->next = head;
ListNode* newTail = head;
for (int i = 0; i < n - s - 1; i++) newTail = newTail->next;
ListNode* newHead = newTail->next;
newTail->next = nullptr;
return newHead;
}JavaScript
var rotateRight = function(head, k) {
if (head === null) return head;
var n = 1, tail = head;
while (tail.next !== null) { tail = tail.next; n++; }
var s = k % n;
if (s === 0) return head;
tail.next = head;
var newTail = head;
for (var i = 0; i < n - s - 1; i++) newTail = newTail.next;
var newHead = newTail.next;
newTail.next = null;
return newHead;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 165 two pointers problems · the whole catalogue
Learn the technique: Two Pointers Technique