Rotate List

Problem

You are given the head of a singly linked list and an integer k. Rotate the list to the right by k places. Rotating right by one takes the last node and moves it to the front; doing this k times shifts every node k positions toward the tail, with nodes that fall off the end wrapping around to the front.

Return the head of the rotated list.

k can be much larger than the length of the list, so rotating by k is the same as rotating by k mod n, where n is the number of nodes.

Examples

Example 1

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Rotate right once → [5,1,2,3,4]; a second time → [4,5,1,2,3].

Example 2

Input: head = [0,1,2], k = 4
Output: [2,0,1]

n = 3, and 4 mod 3 = 1, so this is a single right rotation: the last node 2 moves to the front.

Example 3

Input: head = [], k = 5
Output: []

An empty list (or a single-node list) is unchanged by any rotation.

Constraints

• The number of nodes is in the range [0, 500].
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 10^9 — so k may vastly exceed the list length; always reduce it modulo n.

Think about it first

TL;DR

Close the list into a ring, walk to the new tail, and cut — O(n) time, O(1) space.

Approach 1 — Brute force: rotate one step at a time

The naive idea mirrors the definition: to rotate right once, walk to the last node, detach it, and make it the new head. Repeat k times.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import Optional


def rotateRight(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    if not head or not head.next:
        return head
    for _ in range(k):
        prev = None
        curr = head
        while curr.next:
            prev = curr
            curr = curr.next
        # curr is the last node; move it to the front
        prev.next = None
        curr.next = head
        head = curr
    return head

Complexity: O(n · k) time, O(1) space. Each rotation walks the whole list, and k can be up to 2·10^9 — this times out immediately. The fix is to notice that rotating by k equals rotating by k mod n, and that a single rotation only relinks two pointers.

Approach 2 — Find the split point in two passes

The insight: rotating right by k (after reducing k mod n) means the last k nodes move to the front. Equivalently, the list is cut between index n - k - 1 and n - k (0-based): the node at n - k - 1 becomes the new tail, and the node at n - k becomes the new head. So: measure n, reduce k, walk to the new tail, and relink.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import Optional


def rotateRight(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    if not head or not head.next:
        return head

    # Pass 1: length and the old tail.
    n = 1
    old_tail = head
    while old_tail.next:
        old_tail = old_tail.next
        n += 1

    k %= n
    if k == 0:
        return head

    # Pass 2: walk to the new tail at index n - k - 1.
    new_tail = head
    for _ in range(n - k - 1):
        new_tail = new_tail.next

    new_head = new_tail.next
    new_tail.next = None
    old_tail.next = head
    return new_head

Walkthrough on Example 1 ([1,2,3,4,5], k = 2):

1. Pass 1: n = 5, old_tail = node 5.
2. k = 2 % 5 = 2, nonzero.
3. New tail is at index n - k - 1 = 2 → node 3. Walk two steps: 1 → 2 → 3.
4. new_head = new_tail.next = node 4. Cut: 3.next = None.
5. Reconnect old tail: 5.next = head (1).
6. Result: 4 → 5 → 1 → 2 → 3.

Complexity: O(n) time (two passes), O(1) space.

Approach 3 — Close into a ring, then cut

The insight: link the tail back to the head so the list becomes a circle. Rotating is then just choosing where to break the circle. From the head, step forward n - (k mod n) nodes to reach the new tail, then sever. This avoids tracking two separate pointers for the cut.

flowchart LR
  n1["1"] --> n2["2"] --> n3["3"]
  n3 -. "cut: new tail" .-> n4["4"]
  n4 --> n5["5"]
  n5 -. "close ring, then break" .-> n1

For [1,2,3,4,5] with k = 2: close the ring (5 → 1), walk to the new tail (node 3), then cut so node 4 becomes the new head.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import Optional


def rotateRight(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    if not head or not head.next:
        return head

    # Find length and close the ring.
    n = 1
    tail = head
    while tail.next:
        tail = tail.next
        n += 1
    tail.next = head  # now it's a circle

    # New tail sits steps_to_new_tail nodes from the head.
    steps_to_new_tail = n - (k % n)
    new_tail = head
    for _ in range(steps_to_new_tail - 1):
        new_tail = new_tail.next

    new_head = new_tail.next
    new_tail.next = None
    return new_head

Walkthrough on Example 2 ([0,1,2], k = 4): n = 3; close ring 2 → 0. steps_to_new_tail = 3 - (4 % 3) = 3 - 1 = 2. Walk 2 - 1 = 1 step from head: new_tail = node 1. new_head = 1.next = 2; cut 1.next = None. Result 2 → 0 → 1.

Complexity: O(n) time, O(1) space. When k % n == 0, steps_to_new_tail = n, so new_tail lands on the original tail and the list returns unchanged — the ring trick handles this without a special case.

Common pitfalls

• Not reducing k: with k up to 2·10^9, forgetting k %= n either times out or overflows a step counter in stricter languages.
• k % n == 0: the rotation is a no-op; return the original head. In the two-pass version you must guard this explicitly (otherwise you cut at the tail and drop the last node’s link).
• Empty or single-node list: return head immediately; head.next is None and the length logic would need special casing otherwise.
• Off-by-one on the walk: the new tail is n - k - 1 steps from the head (take n - k - 1 .next moves), not n - k. In the ring version, walk steps_to_new_tail - 1 times.
• Forgetting to break the ring: if you close the list into a circle you must sever new_tail.next, or you return a cyclic list.

Pattern takeaway

For rotations and “move the last k to the front” problems on linked lists, reduce k modulo the length first, then relink a constant number of pointers rather than moving nodes one at a time. Closing the list into a ring turns a rotation into a single choice of cut point — a reusable trick whenever a linear structure needs to wrap around.