Reverse Linked List
easyTime: O(n)Space: O(1)
The shape of the problem
Reverse a singly linked list in-place and return the new head. No array, no recursion depth tricks required.
Signals to notice
in-place pointer rewiringlinked list traversalno extra storage
Brute force first
Dump values into an array, reverse the array, rebuild the list. O(n) extra space and a full rewrite.
The key insight
Reversing a list is just flipping each node’s `next` from "what came after" to "what came before". Doing it during the walk needs only the previous node’s address.
Trace it on head=1→2→3
prev=null curr=1 (save nxt=2) 1.next=null prev=1 curr=2 prev=1 curr=2 (save nxt=3) 2.next=1 prev=2 curr=3 prev=2→1 curr=3 (save nxt=null) 3.next=2 prev=3 curr=null curr is null → return prev: 3→2→1
What must stay true
Before each iteration, `prev` is the head of the already-reversed prefix and `curr` is the head of the not-yet-reversed suffix. No node has been lost.
Shape of the loop
prev, curr = None, head while curr: nxt = curr.next curr.next = prev prev, curr = curr, nxt return prev
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Overwriting `curr.next` before saving it. Without the `nxt` temporary, you lose the rest of the list and the loop runs forever or crashes.