Reversing a Linked List
Flip every pointer.
Reversing a linked list is the most asked linked list question in interviews. The trick is to walk along the list once, and turn every arrow around as you go. Pause, and imagine the arrows flipping, one by one.

- The most asked linked list question
- Walk along once
- Turn every arrow around
Three pointers
We keep three pointers. Previous starts as none. Current is the node we're working on. Before we flip current's arrow, we save the next node, so we don't lose the rest of the list. Then current points back to previous, and both pointers step forward. Run it. One, two, three, four, becomes four, three, two, one.
from node import build, show
def reverse(head):
prev = None
current = head
while current:
nxt = current.next
current.next = prev
prev = current
current = nxt
return prev
head = build([1, 2, 3, 4])
show(head)
show(reverse(head))1 -> 2 -> 3 -> 4 -> None 4 -> 3 -> 2 -> 1 -> None
Also uses node.py
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def build(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def show(head):
vals = []
while head:
vals.append(str(head.value))
head = head.next
print(" -> ".join(vals) + " -> None")Why it works
At every step, everything behind current is already reversed, and starts at previous. Everything ahead is untouched, and starts at next. When current falls off the end, previous is the new head. It's O of N time, and O of one extra space.
| key | value |
|---|---|
| prev | the reversed part |
| current | the node being flipped |
| nxt | saved, so we don't lose it |
| Cost | O(n) time, O(1) space |
Summary
Save next, flip the arrow, step forward. Three pointers reverse a linked list in one pass. Next, a clever trick with two pointers moving at different speeds.
Key takeaways- Save next
- Flip current.next
- Return prev