DSA
Rotate List
Covers: Naive, Optimal (circular link). Optimal — Time O(n), Space O(1).
Practice here
Given the head of a linked list, rotate the list to the right by k places.
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
Example 2:
Input: head = [0,1,2], k = 4
Output: [2,0,1]
Naive Approach#
Find the new tail (the (n - k % n - 1)th node), cut the list there, and reattach the back portion to the front. Requires computing the length first and then walking to the split point — two passes total.
cpp
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(!head || !head->next || k == 0) return head;
// compute length
int n = 1;
ListNode* tail = head;
while(tail->next) { tail = tail->next; n++; }
k = k % n;
if(k == 0) return head;
// walk to the new tail (n - k - 1 steps from head)
ListNode* newTail = head;
for(int i = 0; i < n - k - 1; i++)
newTail = newTail->next;
ListNode* newHead = newTail->next;
newTail->next = nullptr;
tail->next = head;
return newHead;
}
};
Time Complexity: O(n)
Space Complexity: O(1)
Optimal Approach: Circular Link#
Instead of tracking a separate tail pointer, close the list into a ring first, then walk to the break point and reopen it. This is one clean pass after the length calculation.
- Find the length and the tail in one traversal.
- Reduce k = k % n — rotating by a full cycle changes nothing.
- The new tail sits at position n - k - 1 (0-indexed from head).
- Connect the old tail to the old head (close the ring).
- Advance to the new tail, record newHead = newTail->next, then cut: newTail->next = nullptr.
cpp
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(!head || !head->next || k == 0) return head;
// Step 1: find length and tail
int n = 1;
ListNode* tail = head;
while(tail->next) { tail = tail->next; n++; }
k = k % n;
if(k == 0) return head;
// Step 2: close the ring
tail->next = head;
// Step 3: walk to the new tail (n - k - 1 steps)
ListNode* newTail = head;
for(int i = 0; i < n - k - 1; i++)
newTail = newTail->next;
// Step 4: break the ring
ListNode* newHead = newTail->next;
newTail->next = nullptr;
return newHead;
}
};
Time Complexity: O(n)
Space Complexity: O(1)