Rotate List — Find Length and Reconnect

Problem 219 · Rotate List

Difficulty: Medium · Pattern: Find Length + Reconnect

Intuition

Find length n; connect tail to head (circular)
New tail is at position n - k % n - 1
Break there, return new head

Solutions

# Python
def rotateRight(head, k):
    if not head or not head.next or k == 0: return head
    tail = head; n = 1
    while tail.next: tail = tail.next; n += 1
    k = k % n
    if k == 0: return head
    tail.next = head  # make circular
    steps = n - k
    new_tail = head
    for _ in range(steps - 1): new_tail = new_tail.next
    new_head = new_tail.next
    new_tail.next = None
    return new_head

// Java
public ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null || k == 0) return head;
    ListNode tail = head; int n = 1;
    while (tail.next != null) { tail = tail.next; n++; }
    k = k % n;
    if (k == 0) return head;
    tail.next = head;
    ListNode newTail = head;
    for (int i = 0; i < n-k-1; i++) newTail = newTail.next;
    ListNode newHead = newTail.next;
    newTail.next = null;
    return newHead;
}

Complexity

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