Given the head of a singly linked list, reverse it and return the new head. A ListNode has an int val and a next reference; the list ends where next is null (None in Python). You may create nodes with ListNode(val), though reversal needs none.
Examples
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2]
Output: [2,1]
Example 3:
Input: head = [1]
Output: [1]
Example 4:
Input: head = []
Output: []
Linked lists — a node holds a value and a next reference, and rearranging a list means moving references, never values. Dummy heads: a node in front of the list so the first element stops being a special case. Two pointers on a list — one ahead of the other, or one moving twice as fast.
How to think about it
1. Three Pointers, One Pass Optimal
Intuition
Reversing a list is repointing each node at the one behind it. The only difficulty is that following next AFTER changing it loses the rest of the list — so hold the next node before you overwrite anything. When the walk falls off the end, the node you were carrying as "previous" is the new head, and the empty list needs no special case at all.
Algorithm
1. Start with previous as null and current at the head. 2. Save current.next before touching it. 3. Point current.next at previous. 4. Advance previous to current and current to the saved next. 5. Return previous.
Time & Space
Time O(n). Space O(1). The recursive version is O(n) stack, which is worth naming as the tradeoff.