Quick Overview
Reversing a list in place is three pointers and one loop: remember `next`, flip the link backwards, step forward. Nothing is copied, so it costs `O(1)` extra space.
Unlike arrays, a Linked List stores elements in separate heap-allocated nodes where each node contains a value and a pointer (next) referencing the following node.
Array: [ 10 | 20 | 30 ] (Single contiguous block of memory addresses)
Linked List: [ 10 | * ] ──> [ 20 | * ] ──> [ 30 | null ] (Scattered memory nodes)
Node 1 Node 2 Node 3
Reversing a linked list in-place requires 3 pointers (prev, curr, next) to reorient pointers without allocating new memory:
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 nextTemp = curr.next; // 1. Save reference to next node
curr.next = prev; // 2. Reverse pointer backwards
prev = curr; // 3. Move prev pointer forward
curr = nextTemp; // 4. Move curr pointer forward
}
return prev; // 'prev' is now the new head of the reversed list!
}
Before: null <── [prev] [curr] ──> [nextTemp] ──> ...
│ │
Action: └─── [curr.next = prev]
| Operation | Array | Linked List |
|---|---|---|
| Insert / Delete at Head | O(N) (Shifting elements) | O(1) (Update head pointer) |
Index Access list[i] | O(1) (Direct lookup) | O(N) (Traverse from head) |
| Search by Value | O(N) | O(N) |
curr.next before reassigning curr.next = prev severs the rest of the list, losing all remaining nodes in memory!Use linked lists when frequent head insertions/deletions are required. Next, let's explore Stacks and the Monotonic Stack Pattern!
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.