reverse-linked-list

Difficulty: Easy · Topic: Linked List · Practice it on parikshan: /practice/reverse-linked-list/start

The story

A kernel-style slab allocator maintains a singly linked free-list of memory blocks: each free block stores a next pointer to the next free block of the same size class. Linux's SLAB/SLUB allocators do this; classic Knuth-style allocators do it; almost every embedded RTOS does it. On certain debug paths the allocator must walk the free-list in the opposite order it was built (for cache-warm reuse, deterministic-allocation replay, or LIFO-to-FIFO reordering during shutdown). The allocator cannot rebuild the list from a side buffer (the free blocks are the only memory available; that is the entire point of a free-list) and cannot afford to copy thousands of pointers to a scratch area and back. It must flip the arrows in place, in one pass, mutating only the next field of each block header.

reverse-linked-list is the canonical version of that operation. It is also the muscle memory every other linked-list problem reuses: middle-of-linked-list, palindrome-linked-list, and add-two-numbers all lean on the three-pointer dance below.

What's actually being asked

Given the head of a singly linked list, reverse the list and return the new head. Empty input returns empty output. The list has at most 100,000 nodes; the algorithm must run in linear time with constant extra space.

The naive approach

Walk the list once, copying each value into an array, then walk the array in reverse, building a brand-new linked list. O(n) time, O(n) extra space. Functionally correct. It misses the point: the question is here to test whether you can manipulate pointers without an auxiliary buffer.

A recursive variant of the in-place reversal uses O(n) stack space; that is also borderline correct but blows up Python's recursion limit on a 100,000-node list. Iterative is the only safe answer here.

The key insight

The list is A -> B -> C -> D -> null. To reverse it, you want null <- A <- B <- C <- D, i.e., each node's next pointer flipped to point to its predecessor. Walk one pointer along the list and at every step, flip the link between the current node and its predecessor.

The catch: the moment you write curr.next = prev, you have destroyed the original curr.next. You can no longer advance to the next node. So you must save it first: nxt = curr.next before the flip. Three pointers (prev, curr, nxt) are the minimum that makes the dance work.

This is the three-pointer dance. Every later linked-list problem that reverses a sublist, sublist range, or alternating pair reuses these three lines:

nxt = curr.next        # save the future
curr.next = prev       # flip the present
prev = curr            # the present becomes the past
curr = nxt             # advance to the saved future

Step-by-step approach

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    prev, curr = None, head
    while curr is not None:
        nxt = curr.next       # 1. save what comes after curr
        curr.next = prev      # 2. flip curr's pointer
        prev = curr           # 3. advance prev to the just-flipped node
        curr = nxt            # 4. advance curr to the saved next
    return prev               # prev is now the new head

Loop invariant in English: the prefix already walked, ending at prev, has been reversed in place; curr points at the start of the rest of the original list. When curr becomes null, the whole list has been reversed and prev holds the new head.

The order of the four lines is non-negotiable. Swap line 1 and line 2 and you have lost the rest of the list. This is the bug AI agents commit most often on linked lists.

Worked example

Input: 1 -> 2 -> 3 -> 4 -> 5 -> null (n = 5).

Initial: prev=null, curr=1.

Iter	nxt	After `curr.next = prev`	New prev	New curr
1	2	1 -> null	1	2
2	3	2 -> 1	2	3
3	4	3 -> 2	3	4
4	5	4 -> 3	4	5
5	null	5 -> 4	5	null

Loop ends. Return prev = 5. The new list is 5 -> 4 -> 3 -> 2 -> 1 -> null. ✓

Counter-cases:

Empty (head = null): loop never runs, returns prev = null.
Single node (head = [42]): loop runs once, returns the same node with next = null.

Both pass without special branching. That is the gift of correct pointer initialisation: the empty and singleton cases collapse to the general one.

Complexity

Time: O(n). Each node's next pointer is rewritten exactly once.
Space: O(1). Three pointer variables, regardless of n.

Common pitfalls

Lost-tail bug: writing curr.next = prev before saving nxt = curr.next truncates the list after one step. The agent-generated version of this code often inlines steps and gets the order wrong. This is the bug the Linked List primer specifically warns about.
Returning head instead of prev. The original head is now the new tail; returning it gives the caller a one-node list. Return prev.
Recursion blowing the stack. The recursive form is elegant on paper and dies at n = 1000 in CPython (default recursion limit). Iterative is the only safe production form.
Mutating an immutable input contract. Some specs forbid mutation. In that case you copy values to an array and build a fresh list; the problem becomes trivially O(n) space. Read the contract.

Where this shows up in the enterprise

Kernel and embedded-RTOS free-lists: as in the opening story. Linux SLAB/SLUB, FreeRTOS xList, and most allocators keep free blocks on a singly linked list. Reversal is occasionally needed for LIFO-to-FIFO conversion and cache-warm replay.
Compiler IR passes: traversing a basic block's instruction list in reverse for dataflow analysis (liveness, reaching-definitions). LLVM's BasicBlock and GCC's gimple_seq both support in-place reversal as a primitive.
Undo stacks in editors and players: a singly-linked history where the most-recent action is the head; presenting the history in chronological order is a reversal.
Linux kernel sk_buff queues: socket buffers chained for packet I/O; certain protocol stacks reverse the chain during teardown or fragmentation handling without copying payloads.
Git plumbing on commit lists: an in-memory commit list reversed for chronological display in tools that walk parent pointers from HEAD backwards.
Symbol-table chaining in linkers: hash-bucket chains built in insertion order, traversed in reverse during one of the resolution passes.

The pattern shows up wherever a linked structure is the right data structure (memory layout, O(1) splice cost, allocator-free chaining through embedded next fields) and the consumer wants to view it in the opposite direction.

Variants you'll see elsewhere

reverse-linked-list-ii: reverse only positions left..right (a sublist). Same three-pointer dance, plus a "stitch" step to reconnect the reversed sublist to the surrounding list. The Linked List palindrome-linked-list problem uses this directly.
reverse-nodes-in-k-group: repeat the dance every k nodes. The cleanest implementation reuses reverse-linked-list as a primitive.
swap-nodes-in-pairs: a special case of reverse-nodes-in-k-group with k=2.
palindrome-linked-list: reverses the second half and compares; the second-half reversal is this exact function.
add-two-numbers-ii: digits stored most-significant-first; reverse both lists, run add-two-numbers, reverse the result.

If reverse-linked-list is muscle memory, the entire cluster collapses to "find the boundary, reverse the right segment, stitch".

How parikshan turns this into a learning loop

Recommended sequence on parikshan:

Open this problem in practice mode with AI off. Draw a 5-node list on paper. Cross out arrows as you flip them. Watch the three-pointer dance with your hand, not the keyboard.
Code the iterative version. Run public tests.
The dynamic private tests generated per session will throw: empty list, single node, two nodes, and 100,000 nodes. A correct three-pointer template passes all four; a recursive solution dies on case 4 with a RecursionError.
Re-solve with recursion (turn the limit up first with sys.setrecursionlimit). Note the difference in feel. The iterative version is the production form; the recursive version is the interview-trick form. Both are good to have.

When you can write the four lines without re-reading the article, you have linked-list pointer reasoning in your fingers. Every other Linked List problem becomes cheaper from here.

In the AI-integrated workspace

Cursor, Copilot, and Claude Code write reverse-linked-list correctly about 90% of the time on the iterative pattern and about 70% of the time on the recursive pattern. The 10% iterative failures are almost always the lost-tail bug: the agent inlines curr.next = prev before saving nxt = curr.next, and the test on a 3-node list returns a 1-node result. The test on the 5-node sample passes if the agent happened to write the steps in the right order; the test on the 100,000-node private input fails silently.

Verification ritual on every agent-generated linked-list reversal:

Read the line that writes curr.next. Is nxt = curr.next saved on the previous line? If not, reject.
Read the return statement. Must be prev, not head.
Trace by hand on the empty list and the single-node list. If the agent added a special-case guard for either, the algorithm is over-fitted; the correct version handles both without branches.

The deeper lesson: linked-list code is where AI agents most reliably write plausible but wrong code, because the bug does not show on length-1 or length-2 inputs and the surface looks the same as the correct version. A senior engineer treats every linked-list reversal as needing the three-question check above. parikshan trains exactly that habit, and the Linked List primer points to this article as the first stop for the muscle memory.