Part 2 · Problems · Linked list
Reverse Linked List
#206 · Easy · LeetCode
Reverse a singly linked list and return the new head.
1->2->3->4->5 -> 5->4->3->2->1
Ask before coding
- Iterative or recursive preferred?
Hint
Three variables: prev, current, next.
Approach
Walk the list. Save next, point current back to prev, move prev and current forward. prev is the new head.
Time O(n) Space O(1)
Watch it run
Solution (JavaScript, tested)
function reverseList(head) {
let prev = null;
while (head) {
const next = head.next; // save before we cut the link
head.next = prev;
prev = head;
head = next;
}
return prev;
}Traps
- Losing the rest of the list by not saving next first.
- Returning head instead of prev.
Say out loud: I'll flip each arrow as I go. I save next before cutting the link.