MediumLinked ListTwo Pointers

Rotate List

1 approach, code in every language

Given the head of a singly linked list and an integer k, shift the whole list to the right by k positions. Rotating right by one means the current tail moves to the front while everything else slides down by one slot.

Because k can be much larger than the list length, rotating by k is the same as rotating by k modulo the length. Return the head of the list after the rotation.

Example 1

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

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

The last two nodes (4 and 5) wrap around to the front while the rest keep their order.

Example 2

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

Output: [2,0,1]

With length 3, rotating by 4 is the same as rotating by 4 % 3 = 1, so only the tail 2 moves to the front.

Constraints

The number of nodes is in the range [0, 500].
-100 <= Node.val <= 100
0 <= k <= 2 * 10^9

Close the Ring, Then Cut

Measure the list, join the tail to the head to form a ring, then break it at the correct spot to produce the rotated head.

Loading animation…

Intuition

A right rotation only changes where the list starts and ends, not the relative order of the nodes. If we temporarily connect the tail back to the head, we get a circle where any node can serve as the head. Rotating right by k means the new head is the node sitting k positions from the end, which is the same as position length minus k from the front. Reducing k modulo the length avoids pointless full loops. Once we walk to the node just before the new head, we snap the ring there and hand back the new head.

Algorithm walkthrough

1Handle trivial cases: an empty list, a single node, or k equal to zero returns head unchanged.
2Traverse to the tail while counting nodes to get the length, then reduce k with k %= length.
3If k becomes zero the list is unchanged, so return head; otherwise connect tail.next to head to form a ring.
4Walk length - k - 1 steps from head to reach the node that will become the new tail.
5Record newTail.next as the new head, cut the ring by setting newTail.next to null, and return the new head.

Implementation

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if head is None or head.next is None or k == 0:
            return head
        length = 1
        tail = head
        while tail.next:
            tail = tail.next
            length += 1
        k %= length
        if k == 0:
            return head
        tail.next = head
        steps_to_new_tail = length - k - 1
        new_tail = head
        for _ in range(steps_to_new_tail):
            new_tail = new_tail.next
        new_head = new_tail.next
        new_tail.next = None
        return new_head

Time

O(n)

Space

O(1)

One pass measures the list and a partial pass finds the cut point; only a few pointers are stored.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Linked List

After the pattern

Now solve one you haven't seen.

Rundown Cue Shift is our own problem on the technique behind Rotate List: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free