Pattern 2: In-place reversal

Reversing a linked list is the most classic problem in this section — and the one that shows up most as a building block of bigger problems. The trick: walk along the list turning each pointer backward, being careful not to lose the rest.

🎯

Try it first: Reverse Linked List

Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.

Reverse a linked list and return the new head. The list is head = ListNode (each node has .val and .next; the last one points to None/null).

Example: 1 → 2 → 3 → 4 → 5 becomes 5 → 4 → 3 → 2 → 1.

(For testing, we pass the list as an array and compare the result as an array.)

Carregando editor…

Did you try? One approach is to copy the values into an array, reverse it, and rebuild — but that spends O(n) memory. The theory below reverses in place, with O(1) space, just by repointing the next pointers.

The theory: turning the pointers, one by one

Reversing the list means each next, which used to point forward, now points backward. The danger: if you do curr.next = previous without first saving where curr pointed, you lose the rest of the list.

That is why the pattern uses three pointers:

prev: the previous node (starts at None — there is nothing before the head);
curr: the current node (starts at the head);
a temporary (seguinte): saves curr.next before overwriting it.

At each step, the dance is always the same:

1. seguinte = curr.next   (save it so you don't lose the rest)
2. curr.next = prev       (turn the pointer backward)
3. prev = curr            (advance prev)
4. curr = seguinte        (advance curr)

When curr reaches None, prev is the last node visited — that is, the new head. Watch the pointers (next) reversing one by one:

Execução real, gravada passo a passo

Carregando Python no navegador (primeira vez demora alguns segundos)…

Why is it O(n) time and O(1) space?

The loop visits each node exactly once (curr walks from start to end), doing O(1) work per node (four assignments) → O(n) time. We create no new structure — just three pointers that walk — so O(1) space. Copying into an array and rebuilding would also be O(n) time, but with O(n) space; in-place reversal is strictly better.

Solution	Time	Space
Copy values to array and rebuild	O(n)	O(n)
In-place reversal (3 pointers)	O(n)	O(1)

The same idea, with a real ListNode

In the editor you manipulate node.next directly. It is the same three-pointer dance:

Carregando editor…

Why mastering this is worth so much

In-place reversal is a Lego brick. Reversing only part of the list, reversing in groups of k (a "hard" problem!), checking whether the list is a palindrome, reordering — all of them use this same three-pointer dance as a subroutine. Whoever automates reversal unlocks half the hard problems in the section. Repeat the dance until it comes out without thinking.

🧠 Quick-check quiz

0/4

1. Why does reversal need to save curr.next in a temporary BEFORE doing curr.next = prev?

2. Why does prev start at None?

3. At the end of the loop (curr == None), what is prev?

4. What is the advantage of in-place reversal over copying into an array?

Summary

Reverse = turn each next backward, with three pointers (prev, curr, temporary).
Save curr.next before overwriting it, or you lose the rest of the list.
O(n) time, O(1) space — better than copying into an array.
It is a Lego brick of many hard problems (reverse in groups, palindrome, reorder).

Next lesson: two pointers at different speeds — the middle of the list and cycle detection.

All lessons in this section