Medium

Rotate List

LAB

Given a linked list encoded as an array, rotate it to the right by k positions and return the resulting values.

EXAMPLES

Example 1

Input
{
  "head": [
    1,
    2,
    3,
    4,
    5
  ],
  "k": 2
}

Output
[
  4,
  5,
  1,
  2,
  3
]

FUNCTION SHAPE

head: intArrayk: int→intArray

SOLUTION NOTE

The key insight is that rotation by k places is equivalent to taking the last k nodes and moving them to the front. By connecting the tail to the head, we form a cycle, then break it at the appropriate position.

This pattern of "connect to form a cycle, then break" is useful in many linked list rotation and reordering problems.

Reveal reference solution +

pythonREFERENCE

def rotateRight(self, head: ListNode, k: int) -> ListNode:
    # Edge cases
    if not head or not head.next or k == 0:
        return head

    # Step 1: Find the length of the list and the tail node
    current = head
    length = 1
    while current.next:
        current = current.next
        length += 1

    # The last node (tail) is now in current
    tail = current

    # Step 2: Calculate the effective rotation
    # If k = length, we end up with the original list
    k = k % length
    if k == 0:
        return head

    # Step 3: Form a cycle by connecting tail to head
    tail.next = head

    # Step 4: Find the new tail position
    # We need to go to the (length - k)th node
    current = head
    for _ in range(length - k - 1):
        current = current.next

    # Step 5: Break the cycle at the right position
    new_head = current.next
    current.next = None

    return new_head

TimeO(n)

SpaceO(1)

Open on LeetCode ↗