#206
Reverse Linked List
Easy Iterative pointer reversal
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Reverse a singly linked list and return the new head.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: make every arrow point the other way.
Why this works: walk once, saving next before flipping cur.next back to prev.
Example: 1 → 2 → 3
prev null, cur 1: 1 → nullcur 2: 2 → 1cur 3: 3 → 2 → 1, head = 3
✦Hints open one at a time
Walk the list and flip each next pointer to point backwards.
Keep three references: prev, cur and the saved next.
Recursive version: reverse the rest, then make head.next point back to head.
↗Approach
prev = null, cur = head. Save next = cur.next, set cur.next = prev, then move prev and cur forward. prev ends as the new head.
</>Solution (Java)
/**
* Definition for singly-linked list (provided by LeetCode):
* class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null, cur = head;
while (cur != null) {
ListNode next = cur.next; // save before breaking the link
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
}!Common mistake
Overwriting cur.next before saving it, which loses the rest of the list.
Complexity
- Time: O(n).
- Space: O(1) iterative (O(n) stack for the recursive version).
Topic: Linked List
🎬 Episodes 40–45: video coming soon