Reverse Linked List II

A localized reversal fails at the boundaries: the middle looks correct, but the prefix disappears, the suffix becomes unreachable, or the returned head is stale. Treat the operation as two reconnections around one controlled reversal.

State the contract and the failure boundary

You are given:

• The head of a singly linked list
• One-based inclusive positions left and right
• The requirement to reverse only the nodes from left through right
• The requirement to return the modified list head

For example:

1 → 2 → 3 → 4 → 5
left = 2, right = 4

The result is:

1 → 4 → 3 → 2 → 5

The values are unchanged. The nodes themselves are reused. Only their next references change.

That gives us the two links that matter most:

1. The node before the range must point to the range's new head.
2. The range's new tail must point to the node after the range.

For this example:

before = 1
range  = 2 → 3 → 4
after  = 5

After reversal:

1 → 4 → 3 → 2 → 5

The prefix link is 1.next = 4. The suffix link is 2.next = 5.

Those are the boundary obligations. If either one is missing, the local reversal may look correct while the complete list is broken.

Two cases deserve immediate attention:

• If left == 1, the reversed range starts at the original head, so the list's returned head changes.
• If left == right, there is nothing to reverse. Return the original head without changing any links.

The clean solution direction is:

1. Add a dummy node before the original head.
2. Move a pointer to the node immediately before position left.
3. Keep the first node in the range fixed as a stable tail.
4. Move each later range node to the front of the range.
5. Return dummy.next.

The dummy node turns “reverse from the head” and “reverse in the middle” into the same pointer problem.

Recognize the localized-reversal pattern

The recognition cue is precise:

Reverse one contiguous positional region, reuse the existing nodes, and preserve the order outside that region.

This is a localized in-place linked-list manipulation problem. The main work is not finding a node by index—singly linked lists do not provide random access. The main work is preserving reachability while changing a small set of links.

Fast and slow pointers are not the primary technique here. They are useful when the problem asks for a midpoint, a cycle, or a relative distance. This problem gives you explicit positions. You need ordinary positional traversal followed by local pointer rewiring.

A straightforward baseline might:

1. Walk to the requested range.
2. Store the target nodes in a Python list.
3. Reverse that auxiliary list.
4. Reconnect the stored nodes.

That can be useful as a debugging reference, but it adds storage and separates the algorithm from the actual ownership structure of the linked list. You are no longer reasoning directly about which node owns which next link.

Another tempting approach is to swap node values rather than rewire nodes. That may produce the expected visible values, but it changes the problem being solved. The requested operation is a node-range reversal, and interviewers generally want you to preserve the existing nodes and manipulate their links.

The optimized criterion is stronger:

Every original node must remain reachable exactly once from the returned head. Only links inside the requested range and at its two boundaries should change.

That criterion will guide the algorithm and the proof.

Name the boundary state before mutation

Before changing any pointer, name the roles.

• dummy: a fixed node whose next points to the original head
• before: the node immediately before position left
• start: the original first node in the requested range
• moved: the next node pulled forward during reversal
• successor: the node after position right

The initial shape is:

dummy → before → start → ... → end → successor

The variable successor is useful for reasoning even though the compact implementation does not need to store it separately. The range tail will eventually point to it.

Why does start remain important after the reversal begins?

Because the original range head becomes the range tail:

Before:  start → node₂ → node₃ → successor
After:   node₃ → node₂ → start → successor

That stable tail is the key to the head-insertion method. Each iteration takes the node immediately after start and inserts it immediately after before.

To locate before, begin at dummy and advance left - 1 times:

for _ in range(left - 1):
    before = before.next

When left == 1, the loop performs zero steps, so before remains dummy. That is exactly what we want. The dummy absorbs the special case where the original head must be replaced.

Derive the head-insertion rewiring

After locating the boundary:

before → start → ...

Suppose start.next is the next node to move:

before → start → moved → remaining

We want:

before → moved → start → remaining

That requires three link updates:

1. Save moved, because the current links are about to change.
2. Bypass moved from its old position.
3. Insert moved after before.

In code:

moved = start.next
start.next = moved.next
moved.next = before.next
before.next = moved

The assignment order matters. If you change start.next before saving moved, you may lose the only direct reference to the node you intended to move.

The number of nodes in the range is:

right - left + 1

The first node, start, is already in the correct position for the beginning of the reversed range. Therefore, we perform exactly:

right - left

head insertions.

The loop invariant is the useful part to remember:

Before each iteration, before.next is the head of the reversed portion, start is the tail of that portion, and start.next is the first node not yet moved—or the successor after the range.

Here is the Python implementation. It assumes the usual ListNode definition supplied by the problem.

class Solution:
    def reverseBetween(
        self,
        head: ListNode | None,
        left: int,
        right: int,
    ) -> ListNode | None:
        if left == right:
            return head

        dummy = ListNode(0, head)

        # Find the node immediately before position left.
        before = dummy
        for _ in range(left - 1):
            before = before.next

        # The original range head becomes the range tail.
        start = before.next

        # Move each later range node to the front.
        for _ in range(right - left):
            moved = start.next
            start.next = moved.next
            moved.next = before.next
            before.next = moved

        return dummy.next

Each variable has one job:

• dummy preserves a uniform return point.
• before owns the connection from the prefix into the range.
• start stays fixed and becomes the range tail.
• moved is the node currently being promoted to the range front.

This is pointer rewiring, not node creation. The algorithm changes references between existing nodes and uses constant auxiliary space.

Prove reachability and correctness

The code is short because the state has been reduced to stable roles. The correctness argument comes from the invariant.

Initialization

After the first traversal:

dummy → ... → before → start → ...

before is immediately before position left. start is the first node in the target range. The reversed portion initially contains one node: start.

A one-node reversed portion is already valid.

Maintenance

At the start of an iteration, the local shape is:

before → reversed portion → start → moved → remaining

The code performs:

moved = start.next
start.next = moved.next
moved.next = before.next
before.next = moved

After those assignments:

before → moved → reversed portion → start → remaining

Exactly one node, moved, has been removed from the unprocessed suffix and inserted at the front of the reversed portion.

The saved reference to moved.next keeps the remaining chain reachable. The link from before keeps the reversed portion connected to the prefix. The link from start keeps the reversed portion connected to the suffix.

Nothing is copied. Nothing is discarded.

Termination

The loop runs right - left times. At that point, every node from position left through position right has been moved into reversed order.

The original start is now the last node in the range. Its next link points to the original successor after position right.

Therefore:

• before.next points to the new range head.
• start.next points to the successor.
• dummy.next points to the complete resulting list.

If left > 1, dummy.next still points to the original head. If left == 1, dummy.next points to the new head created by the reversal.

The reachability proof is the important interview point:

Every iteration moves one existing node without dropping the saved remainder. The prefix remains connected through before, and the suffix remains connected through start. Therefore, the returned list contains every original node exactly once, in the required order.

Dry-run the pointers on a concrete range

Use:

1 → 2 → 3 → 4 → 5
left = 2
right = 4

After locating the boundary:

before = 1
start  = 2

The local shape is:

1 → 2 → 3 → 4 → 5
    ↑       ↑
  start   range end

The loop runs 4 - 2 = 2 times.

Iteration	moved	Operation	Result
1	3	Remove 3 after 2, insert it after 1	1 → 3 → 2 → 4 → 5
2	4	Remove 4 after 2, insert it after 1	1 → 4 → 3 → 2 → 5

Notice what stays fixed:

before = 1
start  = 2

After the first iteration:

before → 3 → start → 4 → 5

After the second:

before → 4 → 3 → start → 5

The final boundary facts are exactly what we planned:

1.next = 4
2.next = 5
dummy.next = 1

The range is reversed, the prefix remains intact, and the suffix remains reachable.

A common mutation-order bug looks like this:

start.next = start.next.next
moved = start.next

This is wrong because start.next no longer refers to the node that was removed. The code has advanced past it and may now move the wrong node. Save the node first. Then change the links.

Validate complexity and edge cases

The algorithm performs two kinds of work:

1. It advances before up to position left.
2. It performs right - left local moves.

Both are bounded by the length of the list, so the total time complexity is:

O(n)

The fixed dummy node and a constant number of pointers are the only extra storage:

O(1) auxiliary space

This excludes the input nodes themselves, which are reused rather than copied.

Check the boundaries deliberately.

left == right

No links should change.

5
left = 1
right = 1

The early return handles this directly.

left == 1

The range begins at the original head. The dummy node makes the new range head attach through dummy.next, so no separate head replacement branch is needed.

1 → 2 → 3 → 4
left = 1
right = 3

4 → 3 → 2 → 1

right == n

The range reaches the end of the list. The original range head, now the range tail, must point to None.

1 → 2 → 3 → 4
left = 2
right = 4

1 → 4 → 3 → 2

The existing start.next = moved.next operation naturally preserves None as the final successor.

Reverse the entire list

This combines both boundary cases:

1 → 2 → 3 → 4 → 5
left = 1
right = 5

5 → 4 → 3 → 2 → 1

The dummy handles the head. The original head becomes the tail.

Singleton list

A one-node list must remain unchanged. With valid positions, left == right, so the early return is sufficient.

Two-node range

For:

1 → 2
left = 1
right = 2

The loop runs once:

2 → 1

This is a useful test because it exposes incorrect assumptions about there always being an unprocessed node after moved.

When debugging an implementation, inspect these facts rather than only comparing printed values:

• Does the returned head come from dummy.next?
• Does the predecessor point to the new range head?
• Does the original range head point to the successor?
• Are all original nodes reachable exactly once?
• Did any link accidentally create a cycle?
• Did the loop perform exactly right - left moves?

The transferable rule

For any in-place linked-list edit over one contiguous region, identify three positions before mutating:

1. The predecessor before the region
2. The region head, which may become the stable tail
3. The successor after the region

Then state the reachability invariant. Save the next node before changing its link. Rewire one connection at a time. Finally, verify both external reconnections.

That is the durable Reverse Linked List II solution: locate the boundary, move nodes to the front, preserve the tail, and return through a dummy node. The pointer names may change in another problem. The ownership logic does not.