Reversing a Linked List
Reversing a linked list is flipping every link so the last node becomes the first. Each node ends up pointing at the node that used to point at it.
Recognition signal
A problem fits this pattern when it asks for a list in reverse order, flipped in place. The nodes stay the same, and only the links change direction.
signals = [
"List must come out in reverse order.",
"Links change direction, nodes stay the same.",
"Flipping happens in place."
]
for line in signals:
print(line)Template: three pointers
The template walks once through the list with three pointers. Each step saves the next node, flips the current link, and shifts all three pointers forward.
class Node:
def __init__(self, value, nxt=None):
self.value = value
self.nxt = nxt
def build(values):
head = None
for value in reversed(values):
head = Node(value, head)
return head
def to_list(head):
out = []
while head is not None:
out.append(head.value)
head = head.nxt
return out
def reverse(head):
prev = None
curr = head
while curr is not None:
nxt = curr.nxt
curr.nxt = prev
prev = curr
curr = nxt
return prev
print(to_list(reverse(build([1, 2, 3]))))Worked problem: two nodes
With two nodes, the flip is a single link change. The second node becomes the head, and the first node points at nothing.
class Node:
def __init__(self, value, nxt=None):
self.value = value
self.nxt = nxt
def build(values):
head = None
for value in reversed(values):
head = Node(value, head)
return head
def to_list(head):
out = []
while head is not None:
out.append(head.value)
head = head.nxt
return out
def reverse(head):
prev = None
curr = head
while curr is not None:
nxt = curr.nxt
curr.nxt = prev
prev = curr
curr = nxt
return prev
print(to_list(reverse(build([10, 20]))))Example
class Node:
def __init__(self, value, nxt=None):
self.value = value
self.nxt = nxt
def build(values):
head = None
for value in reversed(values):
head = Node(value, head)
return head
def to_list(head):
out = []
while head is not None:
out.append(head.value)
head = head.nxt
return out
def reverse(head):
prev = None
curr = head
while curr is not None:
nxt = curr.nxt
curr.nxt = prev
prev = curr
curr = nxt
return prev
values = [4, 8, 12, 16]
print(values)
print(to_list(reverse(build(values))))Key points
- Prev pointer: the node already flipped, which becomes the new head at the end.
- Curr pointer: the node whose link is being flipped right now.
- Next pointer: the saved link to the rest of the list, kept before flipping.
- Save the next node before changing a link, or the rest of the list is lost.
The walk flips each link in turn, from the first node to the last. The last node, 16, ends up with no node before it in the flipped list, so it becomes the head. Reading from the new head gives 16, 12, 8, 4.
Note
at the end, the prev pointer holds the head of the flipped list.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
Before changing a node's link, which node must be saved first?