Reverse Linked List
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Reverse a singly linked list and return the new head.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What does each node need to point to after reversal?
- Hint 2Before you change a node's link you must save where it used to point.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A train of coaches, each coupled to the one in front. To reverse the train you walk along it, and at each coach you un-couple from the next one and re-couple it to the coach behind it. The only danger: once you un-couple, you lose sight of the rest of the train, so first note down which coach is next.
- The obvious way
Copy the values into a list, reverse the list, rebuild the nodes: O(n) extra memory.
- The key insight
Walk the chain with three things in hand: the node in front of you (current), the node you already reversed behind you (previous), and the saved next node. At each coach: save the next one, point current backwards at previous, then step forward. When the walk ends, previous is the new head.
- The algorithm
- previous = nothing, current = head.
- Save current's next node somewhere.
- Make current point to previous (the flip).
- Move previous to current and current to the saved next. Repeat until current is nothing; return previous.
Watch it run
Examplelist = 1 -> 2 -> 3
Standing at 1. Save its next (2). Make 1 point backwards at nothing: it becomes the tail.
reversed so far: 1
Where people slip
- Save current.next BEFORE overwriting it, or the rest of the list is lost.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
# ListNode: .val and .next are provided
def reverse_list(head):
previous = None
current = head
while current:
next_node = current.next # remember the rest of the train
current.next = previous # flip this link backwards
previous = current # step forward
current = next_node
return previousNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.