LeetCode 92: Reverse Linked List II Solution in Python Explained

Problem Statement

In LeetCode 92, you’re given the head of a linked list and two integers left and right (1-indexed positions). Your task is to reverse the nodes from position left to right, inclusive, and return the modified list. This builds on LeetCode 206: Reverse Linked List, adding positional constraints, and differs from decoding tasks like LeetCode 91: Decode Ways.

Constraints

• Number of nodes: 1 <= n <= 500
• Node values: -500 <= Node.val <= 500
• 1 <= left <= right <= n

Example

Let’s see some cases:

Copy codeInput: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Explanation: Reverse nodes 2 to 4 (2,3,4 becomes 4,3,2).

Copy codeInput: head = [5], left = 1, right = 1
Output: [5]
Explanation: Single node, no reversal needed.

Copy codeInput: head = [3,5], left = 1, right = 2
Output: [5,3]
Explanation: Reverse entire list (3,5 becomes 5,3).

These examples show we’re reversing a specific segment.

Understanding the Problem

How do you solve LeetCode 92: Reverse Linked List II in Python? Take head = [1,2,3,4,5], left = 2, right = 4. We need [1,4,3,2,5], reversing 2,3,4 into 4,3,2 while keeping 1 and 5 in place. This isn’t a subset problem like LeetCode 90: Subsets II; it’s about in-place list reversal. We’ll use: 1. Iterative One-Pass: O(n) time, O(1) space—our best solution. 2. Two-Pointer Iterative: O(n) time, O(1) space—an alternative.

Let’s dive into the primary solution.

Solution 1: Iterative One-Pass Approach (Primary)

Explanation

In one pass, locate the segment to reverse, perform the reversal in-place, and reconnect the list. Use pointers to track the node before left, reverse the segment from left to right, and link it back. This is efficient and clear, making it the best solution.

For [1,2,3,4,5], left = 2, right = 4:

• Before: 1.
• Segment: 2,3,4 → 4,3,2.
• After: 5.
• Result: [1,4,3,2,5].

Step-by-Step Example

Assume a ListNode class: class ListNode: def __init__(self, val=0, next=None): self.val = val; self.next = next.

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

Goal: Return [1,4,3,2,5].

• Start: dummy = ListNode(0, head), prev = dummy.
• Step 1: Move to node before left=2.
• prev = 1 (after 1 step).
• Step 2: curr = 2, reverse from 2 to 4.
• Initial: prev = 1, curr = 2, next_node = 3.
• 1st: 2.next = 5, 1.next = 3, curr = 3, [1,3,4,5], con = 2.
• 2nd: 3.next = 2, 1.next = 4, curr = 4, [1,4,3,2,5], con = 2.
• 3rd: 4.next = 3, 1.next = 4, curr = 5, done.
• Finish: Return [1,4,3,2,5].

Example 2: head = [5], left = 1, right = 1

Goal: Return [5].

• Start: prev = dummy.
• Step 1: left=1, prev = dummy.
• Step 2: curr = 5, reverse 1 node (no change).
• Finish: Return [5].

Example 3: head = [3,5], left = 1, right = 2

Goal: Return [5,3].

• Start: prev = dummy.
• Step 1: left=1, prev = dummy.
• Step 2: curr = 3, reverse to 5.
• 3.next = None, dummy.next = 5, 5.next = 3, curr = None.
• Finish: Return [5,3].

How the Code Works (Iterative One-Pass) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

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

def reverseBetween(head: ListNode, left: int, right: int) -> ListNode:
    # Line 1: Create dummy node to handle head reversal
    dummy = ListNode(0, head)
    # Dummy node (val=0, next=head) simplifies cases where left=1
    # e.g., dummy -> 1 -> 2 -> 3 -> 4 -> 5

    # Line 2: Initialize prev to dummy
    prev = dummy
    # prev starts at dummy, will move to the node before left
    # e.g., dummy initially

    # Line 3: Move prev to node before left position
    for _ in range(left - 1):
        # Loops left-1 times to reach the node before left (1-indexed)
        # e.g., left=2, move 1 time, prev = 1
        prev = prev.next

    # Line 4: Set curr to the start of the segment to reverse
    curr = prev.next
    # curr points to the left position (e.g., 2 for left=2)
    # Will be the first node to reverse

    # Line 5: Initialize con (connection) to the segment start
    con = curr
    # con saves the first node of the segment (e.g., 2)
    # Used later to connect to the end of the reversed segment

    # Line 6: Reverse the segment from left to right
    for _ in range(right - left + 1):
        # Loops right-left+1 times, the length of the segment
        # e.g., right=4, left=2, loops 3 times for 2,3,4

        # Line 7: Store the next node
        next_node = curr.next
        # Saves the next node before we change pointers
        # e.g., curr=2, next_node=3 initially

        # Line 8: Reverse the link
        curr.next = prev.next
        # Points curr to what prev.next was pointing to
        # e.g., first iteration: 2.next = 3 (no change yet, but builds)

        # Line 9: Update prev.next to curr
        prev.next = curr
        # Links prev to curr, moving curr into the reversed position
        # e.g., 1.next = 3, then 1.next = 4

        # Line 10: Move curr to next_node
        curr = next_node
        # Advances curr to the next node to reverse
        # e.g., curr moves from 2 to 3, then 4

    # Line 11: Connect the reversed segment back
    con.next = curr
    # Links the original start of the segment to the node after right
    # e.g., 2.next = 5, connecting 4,3,2 to 5

    # Line 12: Return the modified list
    return dummy.next
    # Returns the head of the list (e.g., 1 -> 4 -> 3 -> 2 -> 5)
    # Skips dummy for the actual head

This detailed explanation ensures the one-pass reversal is clear, efficiently handling the segment.

Alternative: Two-Pointer Iterative Approach

Explanation

Use two pointers to locate the left and right nodes, isolate the segment, reverse it separately, and reconnect. This splits the task into finding bounds and reversing, using extra pointers.

For [1,2,3,4,5], left = 2, right = 4:

• Find 2 and 4.
• Reverse 2->3->4 to 4->3->2.
• Reconnect: 1->4->3->2->5.

Step-by-Step Example (Alternative)

For [1,2,3,4,5], left = 2, right = 4:

• Step 1: prev = 1, start = 2, end = 4, after = 5.
• Step 2: Reverse 2->3->4 to 4->3->2.
• Step 3: 1.next = 4, 2.next = 5.
• Finish: [1,4,3,2,5].

How the Code Works (Two-Pointer)

Copy codedef reverseBetweenTwoPointer(head: ListNode, left: int, right: int) -> ListNode:
    if left == right:
        return head
    dummy = ListNode(0, head)
    prev = dummy
    for _ in range(left - 1):
        prev = prev.next
    start = prev.next
    end = start
    for _ in range(right - left):
        end = end.next
    after = end.next
    curr, next_node = start, start.next
    for _ in range(right - left + 1):
        curr.next = after
        after = curr
        curr = next_node
        next_node = next_node.next if next_node else None
    prev.next = after
    return dummy.next

Complexity

• Iterative One-Pass:
• Time: O(n) – single pass.
• Space: O(1) – constant pointers.
• Two-Pointer Iterative:
• Time: O(n) – multiple passes.
• Space: O(1) – constant pointers.

Efficiency Notes

Iterative One-Pass is the best solution for its O(n) time in a single pass, minimal pointer use, and clarity—Two-Pointer Iterative is a viable alternative but requires more steps.

Key Insights

• One-Pass: Efficient traversal and reversal.
• Pointers: Track segment boundaries.
• In-Place: No extra list needed.

Additional Example

For head = [1,2,3], left = 1, right = 2:

• Goal: [2,1,3].
• One-Pass: Reverse 1->2 to 2->1, connect to 3.

Edge Cases

• Single Node: [1], left=1, right=1 → [1].
• Full List: [1,2], left=1, right=2 → [2,1].
• End Segment: [1,2,3], left=2, right=3 → [1,3,2].

Both solutions handle these seamlessly.

Final Thoughts

LeetCode 92: Reverse Linked List II in Python is a rewarding linked list challenge. The Iterative One-Pass solution shines with efficiency and simplicity, while Two-Pointer Iterative offers a structured alternative. Want more? Try LeetCode 206: Reverse Linked List for full reversal or LeetCode 86: Partition List for list reordering. Ready to practice? Solve LeetCode 92 on LeetCode with [1,2,3,4,5], left=2, right=4, aiming for [1,4,3,2,5]—test your skills now!