Linked List In-place Reversal

Reverse a linked list, or a piece of one, by turning each next pointer around as you walk, using three pointers and no extra memory.

Overview

The idea

A singly linked list only points forward. To reverse it, each node's next must point to the node that came before it. Copying the values into an array and rebuilding the list works, but costs O(n) extra memory. In-place reversal changes the pointers themselves and needs only three variables.

Copy values to an array, rebuild in reverse — O(n) — n reads plus n writes — no
Push nodes on a stack, pop them into a new order — O(n) — 2n — yes
Turn each next pointer around in place — O(1) — n — yes

The pointer trick is also the building block for harder problems: reverse a sublist, reverse in groups of k, check a palindrome, reorder a list.

Three pointers

The loop walks the list with a pointer called curr. Before you turn its pointer around, save curr.next, or the rest of the list is lost. Then point curr.next back at prev, and move both pointers one step forward.

When curr runs off the end, prev is the last node visited, which is the new head. The old head now points to None, so it is the new tail.

A trace

Reversing 1, 2, 3, 4. The two lists show what is reachable from prev and from curr after each step.

start — None — 1 — empty — 1, 2, 3, 4
1 — 1 — 2 — 1 — 2, 3, 4
2 — 2 — 3 — 2, 1 — 3, 4
3 — 3 — 4 — 3, 2, 1 — 4
4 — 4 — None — 4, 3, 2, 1 — empty

Every node is visited once, so the time is O(n). The three variables are the only extra memory, so the space is O(1).

Recursive reversal

The recursive version reverses everything after the head first, then hooks the head onto the end. For head = 1 with the rest already reversed to 4, 3, 2, node 2 is head.next, and head.next.next = head makes 2 point back at 1. Then head.next = None makes 1 the tail.

4 — 4 (base case: no next) — 4
3 — 4 — 4, 3
2 — 4 — 4, 3, 2
1 — 4 — 4, 3, 2, 1

Every call waits for the one below it, so the call stack holds n frames: O(n) space. Python's interpreter has a recursion limit; the default on CPython 3.14 is 1,000, so a recursive reversal of a list with about a thousand nodes raises RecursionError. The iterative version has no such limit. Give the iterative version, and mention the recursive one as a contrast.

Reversing a sublist

Reverse Linked List II asks to reverse only positions left to right (1-indexed). Four nodes matter: the node before the segment, the first node of the segment (which becomes its last), the last node of the segment (which becomes its first), and the node after the segment.

The steps below run on 1, 2, 3, 4, 5 with left = 2 and right = 4.

Put a dummy node in front of the head, so a segment that starts at position 1 has a node before it.
Walk before to position left − 1 (node 1).
Reverse right − left + 1 = 3 nodes with the three-pointer loop, starting at before.next. After the loop, prev is node 4 and curr is node 5.
Reconnect: the segment's old first node (node 2) now points at curr, and before.next points at prev.

2 — 1, 2, 3, 4, 5 — before = node 1
3 — node 1 still points at node 2; the segment is now 4, 3, 2 with node 2 pointing at None — node 2's pointer was flipped to None, then node 3's to 2, then node 4's to 3; curr is node 5
4 — 1, 4, 3, 2, 5 — two links rewired

Only two links change outside the segment, so the reconnection is the whole difficulty of the problem.

Groups of k

Reverse Nodes in k-Group reverses each block of k nodes and leaves a final block shorter than k as it is. Before reversing a block, count k nodes ahead; if the list runs out, stop. Then reverse the block the same way as a sublist, and move the "before" pointer to the block's old first node, which is now its last.

1, 2 (k = 2) — yes — 2, 1, 3, 4, 5
3, 4 — yes — 2, 1, 4, 3, 5
5 — only one node left — 2, 1, 4, 3, 5, unchanged

Each node is visited twice at most, once while counting and once while reversing, so the time stays O(n).

Checking a palindrome

Palindrome Linked List can be solved in O(1) extra space by reversing the second half. Find the middle with a slow pointer (one step) and a fast pointer (two steps). Reverse the list from the middle onward. Walk the first half and the reversed second half together and compare values. Then reverse the second half back, so the caller's list is unchanged.

Middle (slow stops at) — the second 2 — 3
Reversed second half — 1, 2 — 1, 2, 3
Compare with the first half — 1 = 1, 2 = 2 — 1 = 1, 2 = 2
Result — palindrome — palindrome

For an odd length the middle node is in the reversed half and is compared with itself, which is harmless. The comparison loop runs while the reversed half has nodes. The front part of the list, which now ends at the middle node, always has at least that many, so the first pointer never runs out early.

> [!TIP] > Say that you will restore the list. A solution that leaves the input mangled is a real flaw, and the restore is one more call to the same reversal.

The dummy node

A dummy node placed before the head removes special cases when the head itself may change.

Reverse a sublist starting at position 1 — separate branch for the head — before = dummy, same code
Reverse in groups of k — the first group needs its own reconnection — dummy is the first "before"
Return the new head — track it by hand — return dummy.next

What you will be able to do

Reverse a list with three pointers and explain why next must be saved first.
Reverse a sublist and name the two links that change outside it.
Reverse in groups of k, leaving a short final group alone.
Check a palindrome in O(1) extra space and restore the list afterward.
Choose the iterative version and say what the recursive one costs.

When to use it

Reverse a whole singly linked list
Reverse the nodes between two positions and reconnect them
Reverse every block of k nodes, leaving a short final block as it is
Check whether a list is a palindrome without copying it (reverse the second half)
Reorder or interleave a list, which usually reverses the second half first
Any linked list problem that must run in O(1) extra space and change the order of nodes

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio