Reverse Linked List II (LeetCode 92)

The problem

You get the head of a linked list and two 1-indexed positions left <= right. Reverse just the nodes from position left to position right, leave the rest in place, and return the head.

Input:  1 -> 2 -> 3 -> 4 -> 5,  left = 2, right = 4
Output: 1 -> 4 -> 3 -> 2 -> 5

The block 2 -> 3 -> 4 is reversed to 4 -> 3 -> 2; nodes 1 and 5 stay put.

How to think about it

Start with brute force. Copy the values into an array, reverse the slice [left-1 : right], and write the values back. O(n) time and O(n) space, and it changes values rather than links, which interviewers usually rule out.

A better but fiddly idea: cut out the sub-list, reverse it with the standard three-pointer flip, and stitch both ends back. It works in one pass, but you have to track four boundary nodes, and the stitching is where bugs live.

The key insight: head-insertion. Stand on prev, the node just before position left. Call cur = prev.next; it is the first node of the block, and it will end up as the last node of the reversed block. Now repeat right - left times: take the node right after cur and move it to the front of the block (right after prev). Each move pushes one more node to the front, so after right - left moves the block is fully reversed, and the ends are already connected. cur never moves; it just slides backwards as nodes jump over it.

A dummy head handles left = 1. When the reversal starts at the head, the real head changes. A dummy in front gives prev somewhere to stand.

Which pattern is this? Linked-list in-place reversal. The tell is “reverse part of a list in one pass”.

Approach

1. Create d = ListNode(0, head); set prev = d.
2. Move prev forward left - 1 times, so it sits just before position left.
3. Set cur = prev.next.
4. Repeat right - left times:
   • nxt = cur.next (the node to move),
   • cur.next = nxt.next (unhook it),
   • nxt.next = prev.next (point it at the current front of the block),
   • prev.next = nxt (make it the new front).
5. Return d.next.

Solution

class ListNode:                                   # LeetCode's node type
    def __init__(self, val=0, next=None):
        self.val = val; self.next = next

def reverse_between(head, left, right):
    d = ListNode(0, head); prev = d               # dummy handles left == 1
    for _ in range(left - 1): prev = prev.next    # prev = node before position left
    cur = prev.next                               # first node of the block (ends up last)
    for _ in range(right - left):
        # move the node after cur to the front of the block
        nxt = cur.next; cur.next = nxt.next; nxt.next = prev.next; prev.next = nxt
    return d.next
# reverse_between([1,2,3,4,5], 2, 4) -> [1,4,3,2,5]

Dry run

On 1 -> 2 -> 3 -> 4 -> 5, left = 2, right = 4. After step 2, prev is node 1 and cur is node 2.

Two moves (right - left = 2), and the block is reversed. cur (node 2) now points to 5.

Complexity

• Time: O(n). At most one walk to left, then right - left constant-time moves.
• Space: O(1). A dummy node and four pointers.

Edge cases and pitfalls

• left == right: zero moves; the list is returned unchanged.
• left == 1: the head changes. Without the dummy you would return the old head, which is now in the middle.
• right is the last node: cur.next becomes None at the end, which is correct.
• Moving cur inside the loop. cur stays the same node throughout; only nxt changes.
• Off-by-one on the walk. It is left - 1 steps from the dummy, not left.

Related problems

• Reverse Linked List (LeetCode 206): the whole-list version.
• Reverse Nodes in k-Group (LeetCode 25): reverse every block of k, reconnecting the boundaries each time.
• Reorder List (LeetCode 143): reverse the second half, then weave.