Reverse a linked list
We'll cover the following
Reverse a singly linked list in place.
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
cur30
next81
12
93
44
75
26
67
58
109
1210
1111
Save next (8). Point 3 back at null. Move prev and cur forward.
reversed part: null
1 / 13
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(n) | O(1) | Each arrow is flipped once, in place. |
In Python
def reverse(head):
prev = None
while head:
nxt = head.next # remember the rest
head.next = prev # flip the arrow
prev, head = head, nxt # step forward
return prevSummary: say it in the interview
- Walk the list with three names: prev, cur and next. Save next, flip cur to point back at prev, then slide all three forward. Nothing is copied, so memory stays constant.
- Time O(n), space O(1). Each arrow is flipped once, in place.