Reversing In Place

Linked Lists, lesson 2 of 3

Reversing In Place

The three-pointer reversal, traced step by step, plus reversing just a slice of the list.

12 min, 0 of 3 activities solved

Getting Python ready… examples can run in a moment.

Reversal is the linked list move. It shows up on its own and as a step inside bigger problems (palindromes, reordering, k-groups, adding numbers).

The idea: walk the list once and flip each arrow to point backwards. You need three pointers:

prev: the already-reversed part (starts None)
cur: the node being flipped
nxt: a bookmark to the rest, saved before you overwrite cur.next

before:  None   1 -> 2 -> 3 -> None
         prev  cur

step 1:  None <- 1    2 -> 3 -> None
               prev  cur

step 2:  None <- 1 <- 2    3 -> None
                    prev  cur

When cur falls off the end, prev is the new head. O(n) time, O(1) extra space: no new nodes.

Example

Three pointers, traced

Watch the two halves: the reversed part grows at its front while the rest shrinks. Try swapping lines 1 and 2 to see how losing the bookmark cuts the list.

Quiz

The loop runs only twice. What does this print?

[1, 2] [3, 4]

[2, 1] [3, 4]

[2, 1] [4, 3]

[4, 3, 2, 1] []

Example

The recursive version

Elegant, but it uses O(n) call-stack space and Python stops at ~1,000 nested calls. In interviews (and in the practice problems with big inputs) prefer the iterative loop.

Variation: reverse just a slice. To reverse positions left..right (1-indexed):

Put a dummy before the head and walk to before, the node just ahead of the slice.
Run the same three-pointer loop exactly right - left + 1 times starting at before.next.
Reconnect: the slice's old first node is now its last, so point it at cur (the node after the slice), and point before.next at prev.

1 -> [2 -> 3 -> 4] -> 5      left=2, right=4
1 -> [4 -> 3 -> 2] -> 5

Same loop, plus careful stitching. The k-group problem at the end of this unit repeats this for every block of k nodes.

Quiz

Why does the slice reversal start from a dummy node placed before the head?

It makes the loop run faster

So before exists even when left = 1 (the slice starts at the head)

Because reversal needs an even number of nodes

To avoid creating a cycle at the end

Exercise

Reverse a sublist

Write reverse_between(head, left, right) that reverses the nodes at positions left through right (1-indexed, left <= right) and returns the head of the whole list.

[1, 2, 3, 4, 5], left 2, right 4 gives [1, 4, 3, 2, 5].

Rewire the existing nodes in one pass.