Turn the chain around
Reverse a linked list in place by flipping each link to point at the node before it. About 15 minutes.
Flip one link at a time
Walk the chain from the front. At each box, turn its pointer around to aim at the box you just left. The first box then points at nothing, and it becomes the last box of the reversed chain.
There's a catch: once you turn a pointer around, you can no longer follow it forward. So before flipping, save the next box in a variable. Then flip, then move on using the saved one.
prev = None
curr = head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev- curr
- 1
- prev
- none
Box 1: its next is box 2 (saved). Point box 1 at nothing, the box before it.
Who is the new head
When the walk ends, the current box is nothing, and previous is the last box you flipped, which was the old tail. That box is now at the front of the reversed chain, so return it.
The empty list works without a special case: the loop never runs, previous is still nothing, and you return nothing. A list with one box works too: its pointer is flipped to nothing, which it already was.
Why save the next box before flipping a link?
- AAfter flipping, the pointer to the next box is gone, and you wouldn't be able to continue
- BIt makes the loop faster
- CTo make a copy of the list
Show the answer
After flipping, the pointer to the next box is gone, and you wouldn't be able to continue. The flipped pointer aims backwards, so the way forward is lost unless saved.
Reverse the list
Given the head of a singly linked list, reverse the list and return the new head. Reverse it by changing the links, not by creating new nodes.
head = [1, 2, 3, 4] → [4, 3, 2, 1]
0 ≤ number of nodes ≤ 5,000 · -1,000,000 ≤ node.val ≤ 1,000,000