Why it works
- next is saved before cur.next is overwritten, so the rest of the list is never lost: it is the only way to it.
- Everything left of cur is already reversed and starts at prev; each step moves one node from the old list to the front of the reversed one.
- The old head ends up last, pointing to none, and head still points at it. The new head is the last node prev reached.
Complexity
Time O(n): one pass, each node is turned around once. Memory O(1): three pointers, no new nodes.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗