You are given head, the first node of a singly linked list (or nothing, for an empty list).
Reverse the list, so its last node comes first and every next pointer points the other way,
and return the new first node. Rewire the nodes you were given rather than making new ones.
Example 1
- Input
- head = [4, 8, 15]
- Output
- [15, 8, 4]
Example 2
- Input
- head = [7]
- Output
- [7]
A single node is its own reverse.
Constraints
- The list holds 0 to 5000 nodes.
- Every value is between −5000 and 5000.
Show the pattern
Linked list
Reversing in place means rewiring each node's `next` pointer as you pass it, keeping hold of the node behind and the node ahead so nothing is lost.
See linked list in a visualiserShow the approach
Walk the list with two references: prev, the reversed part so far (initially empty), and
node, the next node to move. At each step save node.next, point node.next at prev, then
move prev to node and node to the saved next. When node runs out, prev is the new head.
Time: O(n) · Space: O(1)
Brush up firstLinked List visualiser