The problem
A singly linked list is a chain of nodes, each holding a value and an arrow (next) to the node after it; the last one points to nothing. Given the first node, head, reverse the list and return its new first node.
Examples
01
- Input
head = [1, 2, 3, 4, 5]
- Output
[5, 4, 3, 2, 1]
02
- Input
head = [1, 2]
- Output
[2, 1]
Constraints
- 0 ≤ number of nodes ≤ 5000
- −5000 ≤ Node.val ≤ 5000
The idea
Reversing the list means turning every arrow round. Walk it with two pointers: prev, the part already reversed, and cur, the node being turned.
At each node, first save cur.next — once the arrow is changed it is the only way to reach the rest — then point cur.next at prev, and step both pointers forward. When cur falls off the end, prev is the old last node: the new head.
- Time
- O(n) — each arrow is turned once
- Space
- O(1) — three pointers
Solution · every language run against every case
class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: prev = None # the part already reversed cur = head while cur: nxt = cur.next # remember the rest before cutting it off cur.next = prev # point this node backwards prev, cur = cur, nxt return prev