Reversing a linked list
In one line
Walk the list once with three pointers (prev, cur, next) and flip each node's next pointer to point backwards, reversing the list in O(n) time and O(1) space.
What it is
Reversing a linked list means making the last node the new head and making every next pointer point to the node that used to come before it. You do not move values or create new nodes; you only change links.
The iterative method keeps three references: prev (the already reversed part), cur (the node being processed) and nxt (the rest of the list, saved before the link is broken). The same idea extends to reversing a sub-range, reversing in groups of k, and checking palindromes.
Why interviewers ask
It is one of the most asked linked list questions because it shows whether you can update pointers in the right order without losing nodes. It is also a building block: reverse a sublist, reverse in k-groups, palindrome check, reorder list and add two numbers all reuse it. Interviewers often ask for both the iterative and the recursive versions and their space cost.
How it works
- 1Start with prev = None and cur = head.
- 2Save the rest of the list: nxt = cur.next. Without this, flipping the pointer would lose every node after cur.
- 3Flip the link: cur.next = prev.
- 4Move forward: prev = cur, cur = nxt.
- 5Repeat until cur is None. prev now points to the old tail, which is the new head; return it.
- 6Recursive version: reverse the rest of the list starting at head.next, then set head.next.next = head and head.next = None. It is O(n) time but uses O(n) call stack space, which can overflow on long lists.
Worked example · Reverse 1 -> 2 -> 3 -> None
- Start: prev = None, cur = 1.
- Iteration 1: nxt = 2; 1.next = None; prev = 1, cur = 2. Reversed part: 1 -> None. Remaining: 2 -> 3.
- Iteration 2: nxt = 3; 2.next = 1; prev = 2, cur = 3. Reversed part: 2 -> 1 -> None.
- Iteration 3: nxt = None; 3.next = 2; prev = 3, cur = None. Reversed part: 3 -> 2 -> 1 -> None.
- cur is None, so stop and return prev = 3. Three iterations, three pointer flips, no new nodes.
Picture it
A conga line where everyone holds the shoulder of the person in front. To reverse direction, each person in turn lets go and turns around to hold the person who was behind them. You must remember who was in front before letting go, or that part of the line wanders off.
Reference code
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev, cur = None, head
while cur:
nxt = cur.next # 1. remember the rest of the list
cur.next = prev # 2. flip this node's pointer
prev, cur = cur, nxt # 3. advance both pointers
return prev # prev is the new head
def reverse_between(head, left, right):
"""Reverse positions left..right (1-indexed) in one pass."""
dummy = ListNode(0, head)
before = dummy
for _ in range(left - 1):
before = before.next # node just before the sublist
cur = before.next # becomes the sublist's tail
for _ in range(right - left):
nxt = cur.next # move nxt to the front of the sublist
cur.next = nxt.next
nxt.next = before.next
before.next = nxt
return dummy.next
reverse_list is the three-pointer loop: O(n) time, O(1) space. reverse_between uses a dummy node so left = 1 needs no special case, then moves each next node to the front of the sublist; cur stays as the sublist's tail throughout. Both run in one pass.
Key patterns
Reverse the whole list
When: Return the list in reverse order
How: prev, cur, nxt loop; return prev.
Reverse a sublist
When: Reverse positions left to right only
How: Dummy node, walk to the node before left, then repeatedly move the next node to the front of the sublist (right - left times).
Reverse in k-groups
When: Reverse every block of k nodes, leave a short tail as is
How: Check that k nodes remain, reverse that block, connect the previous group's tail to the new block head, continue.
Reverse the second half
When: Palindrome check, reorder list (L0, Ln, L1, Ln-1, ...)
How: Find the middle with fast and slow pointers, reverse the second half, then compare or interleave the two halves.
Real-world use
Functional language lists
In Erlang, Elixir, Haskell and Clojure, lists are singly linked and prepending is O(1), so the standard idiom is to build a result by prepending and call lists:reverse (or Enum.reverse) once at the end.
Functional queues
Purely functional queues, as in Okasaki's design and Clojure's PersistentQueue, keep a front list and a back list; when the front runs out, the back list is reversed once, giving O(1) amortised enqueue and dequeue.
Garbage collection without a stack
The Deutsch-Schorr-Waite marking algorithm reverses pointers while walking an object graph so the collector can find its way back without an explicit stack, then restores them, which matters when memory is nearly exhausted.
In a project
A chat app stores each conversation's recent messages as a singly linked list with the newest message at the head, because new messages are prepended in O(1). The export feature needs messages oldest first, and it currently copies them into an array and sorts by timestamp.
- Recognise that the list is already in reverse chronological order, so sorting is unnecessary.
- Reverse the list in place with the three-pointer loop, or reverse a copy if other readers still need newest-first order.
- For paginated exports, reverse only the requested range with the reverse-between technique.
- Test with zero, one and two messages and with the maximum conversation size.
Impact: Export drops from O(n log n) with an extra array to O(n) with O(1) extra memory, and long conversations export faster with no extra allocations on the server.
Trade-offs
Use it when
- You need the list in the opposite order and can modify it in place
- A problem needs to compare or combine the two ends of a list (palindrome, reorder)
- You built a list by prepending and need original order
Avoid it when
- Other code still reads the list in its original order: reverse a copy or traverse differently
- You use a doubly linked list: you can just walk from the tail with prev
- The list is very long and you are tempted to use recursion: the call stack can overflow
Cost: Iterative: O(n) time, O(1) space. Recursive: O(n) time, O(n) stack space.
Common mistakes
- Setting cur.next = prev before saving cur.next, which loses the rest of the list.
- Returning head or cur at the end instead of prev; head is now the tail and cur is None.
- In the recursive version, forgetting head.next = None, which leaves a two-node cycle at the end.
- In sublist or k-group reversal, forgetting to reconnect the reversed block to the nodes before and after it.
- Calling the recursive version O(1) space.
Interview questions
Quick revision
- Loop: nxt = cur.next; cur.next = prev; prev = cur; cur = nxt.
- Return prev, not head.
- Iterative O(n) time O(1) space; recursive O(n) stack.
- Recursive: head.next.next = head; head.next = None.
- Sublist: dummy + move-to-front right - left times.
- k-group: check k nodes exist, reverse, reconnect.
- Palindrome / reorder: middle + reverse second half.
Check yourself
1. In the iterative reversal, which line must come first inside the loop?
2. After the loop ends, which pointer is the new head?
3. What is the extra space of the recursive reversal?
4. Reversing 1 -> 2 -> 3 -> 4 -> 5 between positions 2 and 4 gives:
Related
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.