Rotate Linked List

61.Rotate List

Linked List

Two Pointers

Problem Statement:

Given the head of a linked list, rotate the list to the right by k places.

Example:

Input:

head = [1→2→3→4→5]
k = 2

→

Output:

[4→5→1→2→3]

After rotating 2 places to the right: 1→2→3→4→5 becomes 4→5→1→2→3

Algorithm:

1. Handle edge cases (null, single node, k=0)
2. Three main steps:
   • Find length and make list circular
   • Calculate rotation point (length - k % length)
   • Break circular list at rotation point
3. Important:
   • Handle k ≥ length with modulo
   • New head is after new tail
   • Break circular list by setting tail.next = null

Complexity:

Time: O(n) | Space: O(1)

Java Solution:

public ListNode rotateRight(ListNode head, int k) {
    // Handle edge cases
    if (head == null || head.next == null || k == 0) {
        return head;
    }

    // Step 1: Calculate length and make list circular
    ListNode tail = head;
    int length = 1;  // Count head node

    while (tail.next != null) {
        tail = tail.next;
        length++;
    }
    tail.next = head;  // Make circular

    // Step 2: Find new head position
    k = k % length;    // Handle k >= length
    int stepsToNewHead = length - k;

    ListNode newTail = tail;
    while (stepsToNewHead-- > 0) 
        newTail = newTail.next;

    // Step 3: Break circular list at rotation point
    ListNode newHead = newTail.next;
    newTail.next = null;

    return newHead;
}

Python Solution:

def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
    # Handle edge cases
    if not head or not head.next or k == 0:
        return head
        
    # Find length and make circular
    tail = head
    length = 1
    
    while tail.next:
        tail = tail.next
        length += 1
    tail.next = head
    
    # Find rotation point
    k = k % length
    steps = length - k
    new_tail = tail
    
    while steps > 0:
        new_tail = new_tail.next
        steps -= 1
    
    # Break circular list
    new_head = new_tail.next
    new_tail.next = None
    
    return new_head

C++ Solution:

ListNode* rotateRight(ListNode* head, int k) {
    // Handle edge cases
    if (!head || !head->next || k == 0) {
        return head;
    }
    
    // Calculate length and make circular
    ListNode* tail = head;
    int length = 1;
    
    while (tail->next) {
        tail = tail->next;
        length++;
    }
    tail->next = head;
    
    // Find new head position
    k = k % length;
    int steps = length - k;
    ListNode* new_tail = tail;
    
    while (steps--) {
        new_tail = new_tail->next;
    }
    
    // Break circular list
    ListNode* new_head = new_tail->next;
    new_tail->next = nullptr;
    
    return new_head;
}