186. Reverse Linked List
Your function receives the head of a singly linked list. Reverse the list by rewiring the next pointers — the last node becomes the new head, the old head becomes the tail — and return the new head.
The list may be empty (return an empty list) or hold a single node (already reversed). The classic follow-up applies here too: solve it iteratively and recursively, and understand what each version keeps track of.
Example 1:
Input: head = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]
Explanation: Every next pointer is flipped, so traversal now starts at the old tail 5 and ends at the old head 1.
Example 2:
Input: head = [1, 2]
Output: [2, 1]
Explanation: Two nodes swap roles: 2 becomes the head and points at 1, which now ends the list.
Constraints:
- 0 ≤ number of nodes ≤ 5000
- -5000 ≤ node value ≤ 5000
Hints:
Walk the list once carrying two pointers: `prev` (the already-reversed part, initially null) and `curr`. At each node you want to point `curr.next` back at `prev` — but what must you save *before* that write, and why?
Recursively: reverse everything after the head first; that call returns the new head of the reversed tail. The old head's neighbor `head.next` is now the *last* node of that reversed part, so hook yourself on with `head.next.next = head`, then null out `head.next`.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: head = [1, 2, 3, 4, 5]
Expected output: [5, 4, 3, 2, 1]