In-place reversal

55 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A linked list is a chain of boxes, each with a value and an arrow to the next box: 1 → 2 → 3 → 4 → 5. Reverse it, so the arrows point the other way: 5 → 4 → 3 → 2 → 1.

By hand you might copy the values onto paper, read them backwards, and build a new chain: 5 boxes of new paper for a 5-box chain, a million for a million. Or you might try flipping the arrows in place, and immediately hit the problem: as soon as you turn box 1's arrow around (to point at nothing, since it will be the tail), you have lost the arrow that led to box 2, and the rest of the chain is unreachable.

So the whole difficulty is one of bookkeeping: before you flip an arrow, remember where it pointed. That is one extra note, not a million.

Build the structure, one piece at a time

The structure is three pointers into the chain.

Piece 1: cur. The box whose arrow we are about to flip. Starts at the head, box 1.

Piece 2: prev. The box cur's arrow should point to after the flip. Starts as "nothing" (null), because the old head becomes the tail.

Piece 3: next. The one-step memory: before flipping, save cur's old target so we can continue from it.

Each round does four things: save next = cur.next; flip cur.next = prev; step prev = cur; step cur = next.

After round 5, cur is null and prev is box 5, the new head. At every moment the chain is in two pieces: a reversed piece headed by prev and an untouched piece headed by cur.

Why it is correct

The invariant: prev is the head of a correctly reversed chain containing exactly the boxes already processed, and cur is the head of the untouched remainder in original order. No box is lost.

At the start the reversed chain is empty (prev = null) and the untouched chain is the whole list, so it holds. One round takes the head of the untouched chain (cur), saves the rest (next), and points cur at the reversed chain (prev). The reversed chain now has one more box at its front, in the right place, and the untouched chain is next onward, still intact because we saved it before flipping. Both halves of the invariant survive. The loop ends when the untouched chain is empty, so the reversed chain contains everything, and prev is its head.

reversed(x₁ → … → x_k) followed by untouched(x_k+1 → … → x_n) at every round k

The order of the four assignments matters: save next before the flip, flip before moving prev, move prev before moving cur. Get one out of order and you either lose the rest of the chain or create a loop.

Why it is fast

Each round processes one box with four pointer assignments, and there are n boxes.

time = 4n assignments = O(n), extra memory = 3 pointers = O(1)

Copying to a new chain is also O(n) time but O(n) memory, and interviewers usually ask for in place.

How to recognise it in an interview

The cues are "reverse" a linked list or a part of it ("between positions m and n", "in groups of k"), "swap adjacent nodes", or a problem that needs the list read backwards without extra memory, such as checking a palindrome or adding two numbers stored most-significant-first. Say: "I walk with prev, cur and next, flipping one arrow per step; prev heads the reversed prefix and cur the untouched suffix."

Reverse Linked List is the example above. Reverse Nodes in k-Group runs the same loop k boxes at a time and then reconnects the group's old head to the next group. Palindrome Linked List reverses the second half in place and walks both halves together.

02The idea in one line

Walk with prev/cur/next, flipping each pointer.

Reach for it when: Reverse a list, reverse between m and n, reverse in k-groups, swap pairs.

Cost: O(n) time, O(1) space.

03The walk-through, step by step

The video works one example: Reverse 1→2→3→4→5. These are its captions in order, so you can follow without the video or check a step you missed.

1. Three pointers: prev starts at null, cur at the head
2. Save next = 1 before we break the link
3. Flip: node 1 now points to null
4. Advance: prev = 1, cur = 2
5. Save next = 2 before we break the link
6. Flip: node 2 now points to 1
7. Advance: prev = 2, cur = 3
8. Save next = 3 before we break the link
9. Flip: node 3 now points to 2
10. Advance: prev = 3, cur = 4
11. Save next = 4 before we break the link
12. Flip: node 4 now points to 3
13. Advance: prev = 4, cur = 5
14. Save next = null before we break the link
15. Flip: node 5 now points to 4
16. Advance: prev = 5, cur = null
17. cur is null: prev is the new head, every arrow points back
18. One pass, three pointers: O(n) time, O(1) space

04Asked at Google

8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Linked List: Fast and slow pointers, Dummy head and splice, Digit-by-digit with carry, Clone with a map or interleaving.