Interview preparation
Reverse Linked List
1Problem statement
Given the head of a singly linked list, reverse the list and return the new head.
2Examples
3Constraints
- 0 ≤ number of nodes ≤ 5000
- −5000 ≤ Node.val ≤ 5000
4Approaches
Approach 1
Brute Force
Copy values into an array, then write them back in reverse order.
Approach 2
Better: Recursion
Reverse the rest of the list recursively, then make head.next.next = head and head.next = null.
Approach 3
Optimal: Iterative pointer reversal
Walk the list with prev, curr, next pointers, flipping curr.next to point backwards each step.
5Code (optimal approach)
Complete programs that print the example outputs — verified in JavaScript, Python, Java and Go.
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function reverseList(head) {
let prev = null;
let curr = head;
while (curr !== null) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
function build(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) head = new ListNode(values[i], head);
return head;
}
function show(head) {
const out = [];
for (let n = head; n !== null; n = n.next) out.push(n.val);
out.push("null");
return out.join(" -> ");
}
console.log(show(reverseList(build([1, 2, 3, 4, 5]))));
console.log(show(reverseList(build([1, 2]))));
6Complexity
Time
O(n)
Space
O(1)
7Visual walkthrough
- 1.prev = null, curr = 1
- 2.save next = 2; 1.next = null; prev = 1; curr = 2
- 3.save next = 3; 2.next = 1; prev = 2; curr = 3
- 4.…repeat until curr is null; prev (5) is the new head
Related visualization (Singly Linked List Insertion) — shows the core data-structure operations this solution relies on:
Inserts a new node at a given position: walk to the node just before the position, point the new node at its successor, then re-link the predecessor to the new node.