Leetcode 61: Rotate List

1. Problem Statement (Simple Explanation)

You’re given:

• The head of a singly linked list.

• An integer k.

You must rotate the list to the right by k places and return the new head.

Rotating right by 1 place means:

• Move the last node to become the new head.

Rotating right by k places means doing that k times (but we’ll do it more efficiently).

2. Examples

Example 1:

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

Rotate right by 1 step: [5,1,2,3,4]
Rotate right by another step: [4,5,1,2,3]

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

Example 2:

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

Length n = 3, so rotating by k = 4 is same as rotating by k % n = 4 % 3 = 1.

Rotate right by 1: [2,0,1]

Output: [2,0,1]

3. Approach – Make It Circular, Then Break

Naively rotating k times is O(n*k), too slow when k is large. We can do it in O(n).

Steps:

1. Edge cases:

• If head == null or head.next == null or k == 0, just return head.

2. Compute length and get last node:

• Traverse the list to get:

• n (length of list)

• tail (last node)

3. Reduce k:

• A full rotation by n returns the same list:

• k = k % n

• If k == 0 after this, return head.

4. Make the list circular:

• tail.next = head (temporarily connect tail to head).

5. Find new tail and new head:

• New tail is at position n - k (1-based) from the start.

• New head is newTail.next.

• To find newTail, start from head and move n - k - 1 steps.

6. Break the circle:

• newHead = newTail.next

• newTail.next = null

Return newHead.

Example Walkthrough – [1,2,3,4,5], k=2:

• Length n = 5.

• k = 2 % 5 = 2.

• Connect tail to head: [1,2,3,4,5, (points to 1)] – circular.

• New tail position from start: n - k = 3 → node 3 is new tail.

• New head: node after 3 → 4.

• Break at 3: result [4,5,1,2,3].

Pseudo-code:

(Off-by-one details will be adjusted in code; some implementations move length - k - 1 or length - k steps.)

4. Java code

5. C code

6. C++ code

7. Python code

8. JavaScript code