LeetCode 61: Rotate List Solution in Python Explained

Problem Statement

LeetCode 61, Rotate List, is a medium-level problem where you’re given the head of a singly linked list and an integer k. Your task is to rotate the list to the right by k places and return the new head. Each rotation moves the last node to the front, and (k) can be larger than the list length, requiring normalization.

Constraints

• Number of nodes in the list is between 0 and 500.
• -100 <= Node.val <= 100: Node values are within this range.
• 0 <= k <= 2 * 10^9: \(k\) can be very large.

Example

Copy codeInput: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
Explanation: Rotate twice:
[1,2,3,4,5] -> [5,1,2,3,4] -> [4,5,1,2,3]

Input: head = [0,1,2], k = 4
Output: [2,0,1]
Explanation: Rotate 4 times, length = 3, effective k = 1: [0,1,2] -> [2,0,1]

Input: head = [], k = 1
Output: []
Explanation: Empty list remains empty.

Understanding the Problem

How do you solve LeetCode 61: Rotate List in Python? For head = [1,2,3,4,5] and k = 2, rotate the list right by 2 to get [4,5,1,2,3]. Each rotation moves the last node to the front, and (k) may exceed the list length, so we normalize it. We’ll explore two approaches: a Two-Pointer with Length Calculation Solution (optimal and primary) and an Alternative with Circular Array Simulation (intuitive but less efficient for linked lists). The two-pointer method runs in O(n) time with O(1) space.

Solution 1: Two-Pointer with Length Calculation Approach (Primary)

Explanation

Calculate the list length, normalize (k) to (k \% length), and use two pointers to split the list at the new tail (length - k) and reconnect it circularly. Make the list a loop, then break it at the right spot to form the rotated list.

Here’s a flow for [1,2,3,4,5], k = 2:

Copy codeLength = 5, k = 2
New tail = 3 (5-2), new head = 4
Connect 5->1, break 3->4
Result: [4,5,1,2,3]

1. Handle Edge Cases.

• Empty list or \(k = 0\), return head.

2. Calculate Length.

• Traverse to find list length and last node.

3. Normalize (k).

• \(k = k \% length\), connect last to head.

4. Split and Rotate.

• Move to new tail, set new head, break link.

5. Return New Head.

Step-by-Step Example

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

We need [4,5,1,2,3].

• Goal: Rotate list right by 2.
• Result for Reference: [4,5,1,2,3].
• Start: head = [1,2,3,4,5], k = 2.
• Step 1: Calculate length.
• Traverse: 1->2->3->4->5, length = 5, last = 5.
• Step 2: Normalize k.
• k = 2 % 5 = 2, last.next = head, list = [1,2,3,4,5]->1 (circular).
• Step 3: Find new tail (length - k = 5-2 = 3).
• Move 3 steps: 1->2->3, new_tail = 3, new_head = 4.
• Step 4: Break link.
• new_tail.next = None, list = [4,5,1,2,3].
• Finish: Return new_head (4).

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

We need [2,0,1].

• Start: length = 3, k = 4 % 3 = 1.
• Step 1: Connect 2->0, circular list.
• Step 2: New tail = 2 (3-1), new_head = 2.
• Move 2 steps: 0->1, new_tail = 1, new_head = 2.
• Step 3: 1.next = None, list = [2,0,1].
• Finish: Return 2.

How the Code Works (Two-Pointer with Length Calculation)

Here’s the Python code with line-by-line explanation:

Copy codeclass ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def rotateRight(head: ListNode, k: int) -> ListNode:
    # Line 1: Handle edge cases
    if not head or not head.next or k == 0:
        return head

    # Line 2: Calculate length and find last node
    length = 1
    last = head
    while last.next:
        last = last.next
        length += 1

    # Line 3: Normalize k and make circular
    k = k % length
    if k == 0:
        return head
    last.next = head

    # Line 4: Find new tail and head
    steps_to_new_tail = length - k
    new_tail = head
    for _ in range(steps_to_new_tail - 1):
        new_tail = new_tail.next
    new_head = new_tail.next

    # Line 5: Break circular link
    new_tail.next = None

    # Line 6: Return new head
    return new_head

Alternative: Circular Array Simulation Approach

Explanation

Simulate rotation by converting the linked list to a list, performing the rotation as an array operation (shift elements), and rebuilding the linked list. This is less efficient due to O(n) space but mirrors array rotation logic.

1. Convert to List.
2. Rotate Array.

• Shift elements right by \(k \% n\).

3. Rebuild Linked List. 4. Return New Head.

Step-by-Step Example (Alternative)

For [1,2,3,4,5], k = 2:

• Start: Convert to [1,2,3,4,5].
• Step 1: Normalize k = 2 % 5 = 2.
• Step 2: Rotate: [4,5,1,2,3].
• Take last 2: [4,5], prepend to [1,2,3].
• Step 3: Rebuild list: 4->5->1->2->3.
• Finish: Return head (4).

How the Code Works (Circular Array Simulation)

Copy codeclass ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def rotateRightArray(head: ListNode, k: int) -> ListNode:
    # Line 1: Handle edge cases
    if not head or not head.next or k == 0:
        return head

    # Line 2: Convert to list
    arr = []
    curr = head
    while curr:
        arr.append(curr.val)
        curr = curr.next

    # Line 3: Normalize k and rotate array
    n = len(arr)
    k = k % n
    if k == 0:
        return head
    arr = arr[-k:] + arr[:-k]

    # Line 4: Rebuild linked list
    new_head = ListNode(arr[0])
    curr = new_head
    for val in arr[1:]:
        curr.next = ListNode(val)
        curr = curr.next

    # Line 5: Return new head
    return new_head

Complexity

• Two-Pointer with Length Calculation:
• Time: O(n) – Two passes: length and split.
• Space: O(1) – Only pointers.
• Circular Array Simulation:
• Time: O(n) – Convert, rotate, rebuild.
• Space: O(n) – Store array.

Efficiency Notes

Two-Pointer is O(n) time and O(1) space, optimal for LeetCode 61 as it modifies the list in-place. Circular Array Simulation is O(n) time but O(n) space, less efficient due to extra memory, but it’s a clear alternative for understanding.

Key Insights

Tips to master LeetCode 61:

• Normalize \(k\): Use modulo to handle large \(k\).
• Circular Trick: Connect end to start, then break.
• Pointer Precision: Find exact split point.

Additional Example

For [1,2], k = 1:

• Goal: [2,1].
• Two-Pointer: Length = 2, k = 1, new_tail = 1, new_head = 2.
• Result: [2,1].

Edge Cases

• Empty List: [] – Return [].
• Single Node: [1] – Return [1].
• \(k > n\): [1,2], k = 5 – Normalize to 1, return [2,1].

Final Thoughts

The Two-Pointer with Length Calculation solution is a perfect fit for LeetCode 61 in Python—efficient, in-place, and elegant. For a related challenge, try LeetCode 60: Permutation Sequence to switch to permutation logic! Ready to rotate? Solve LeetCode 61 on LeetCode now and test it with [1,2,3,4,5] and (k=2) or [0,1,2] and (k=4) to master list rotation. Dive in and spin it around!