Reverse Linked List
Understand the problem
Given the head of a singly linked list, reverse the order of the nodes and return the new head.
class ListNode {
val: number
next: ListNode | null
constructor(val: number, next: ListNode | null = null) {
this.val = val
this.next = next
}
}
// Input: 1 → 2 → 3 → null
// Output: 3 → 2 → 1 → nullThe key idea: each node currently points to the next node, and we need it to point back to the previous one.
Save next before changing it, otherwise you lose the rest of the list.
Show the basic approach (slower)
O(n) time, O(n) spacefunction reverseListExtraSpace(head: ListNode | null): ListNode | null {
const vals: number[] = []
for (let node = head; node; node = node.next) vals.push(node.val)
// Overwrite values in reverse order
let i = vals.length - 1
for (let node = head; node; node = node.next) node.val = vals[i--]
return head
}This approach borrows an extra array to hold all the values, then writes them back in reverse.
It costs O(n) extra memory, when flipping the pointers in place is enough.
Optimal solution
O(n) time, O(1) spacefunction reverseList(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null
let curr = head
while (curr) {
const nextNode = curr.next // save next BEFORE rewiring the link
curr.next = prev // reverse the pointer
prev = curr // advance prev
curr = nextNode // advance curr
}
return prev // prev ends on the last node — the new head
}Traverse once, flipping each node's next from pointing forward to pointing backward.
- Three variables —
prev,curr,nextNode— are enough to keep the chain intact. - Because you only flip pointers and never allocate new nodes, the extra memory is O(1) — the optimal approach, better than using an array.
Step-by-step trace
1function reverseList(head: ListNode | null): ListNode | null {2 let prev: ListNode | null = null3 let curr = head4 5 while (curr) {6 const nextNode = curr.next // save next BEFORE rewiring the link7 curr.next = prev // reverse the pointer8 prev = curr // advance prev9 curr = nextNode // advance curr10 }11 12 return prev // prev ends on the last node — the new head13}Edge cases to remember
head = null (empty list) → the loop never runs → return null.
A single node → its next is already null → return that same node.
Two nodes 1→2 → after reversing we get 2→1, correct.
You must save next before assigning curr.next=prev, otherwise the chain breaks.