easy
Reverse Linked List
Given the head of a singly linked list, reverse the direction of every next pointer and return the new head.
Constraints
- 0 ≤ number of nodes ≤ 5000
- -5000 ≤ node value ≤ 5000
Examples
in: head = 1 → 2 → 3 → 4 → 5
out: 5 → 4 → 3 → 2 → 1
Recognition clues
- Pure pointer manipulation on a singly linked list
- Each node needs to point at its predecessor
- Keep three pointers: previous, current, next
Pattern
Linked List ManipulationPointer surgery problems are about maintaining prev, curr, and next so no node becomes unreachable, and a dummy head removes the special case of modifying the first node. Doubly linked lists paired with a hash map give O(1) move-to-front, which is the basis of LRU caches.
Solution
Iterate with prev = null and cur = head. At each node save nxt = cur.next, redirect cur.next = prev, then advance prev = cur and cur = nxt. When cur becomes null, prev is the new head. Saving nxt first is what prevents losing the rest of the list.
time O(n)space O(1)
Alternative approaches
- The recursive version reverses the tail first and then hooks the head after it; it is elegant but uses O(n) stack.
Code it yourself
Solve in
Hints: