Stacks, queues and linked lists · Lesson 13 of 23
Linked lists
Nodes pointing at each other, and the core tricks: the dummy node, reversal and fast/slow pointers.
A linked list is a chain of nodes: each holds a value (val) and an arrow to the next (next). Unlike an array, nodes aren't next to each other in memory.
- Inserting or removing a node when you hold its position: O(1) (change an arrow).
- Reaching node
i: O(n) (walk from the start).
head → 3
7
1
null
Each arrow is next; the last node's next is null.
class ListNode {
constructor(val, next = null) { this.val = val; this.next = next }
}
// Build 3 → 7 → 1 from an array, then walk it
const fromArray = (arr) => arr.reduceRight((next, val) => new ListNode(val, next), null)
const toArray = (head) => { const out = []; for (let n = head; n; n = n.next) out.push(n.val); return out }
let head = fromArray([3, 7, 1])
head = new ListNode(9, head) // insert at the front: O(1)
head.next.next = head.next.next.next // remove the node after 3: O(1)
console.log(toArray(head))Trick 1: reversing with three pointers
- 1class ListNode { constructor(v, n = null) { this.val = v; this.next = n } }
- ▶let cur = new ListNode(1, new ListNode(2, new ListNode(3)))
- 3let prev = null
- 4while (cur) { const next = cur.next; cur.next = prev; prev = cur; cur = next }
- 5console.log(prev.val, prev.next.val, prev.next.next.val)
Variables
| cur | 1 → 2 → 3 |
Output
Trick 2: the dummy node
Many linked-list problems have a special case when the first node changes or disappears. The fix: a fake node before the head (dummy.next = head), returning dummy.next at the end. Now every node has a predecessor and no special if is needed.
Trick 3: fast and slow pointers
class ListNode { constructor(v, n = null) { this.val = v; this.next = n } }
// Floyd's cycle check: the fast pointer laps the slow one only if there's a loop
function hasCycle(head) {
let slow = head, fast = head
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
if (slow === fast) return true
}
return false
}
const a = new ListNode(1, new ListNode(2, new ListNode(3)))
console.log(hasCycle(a))
a.next.next.next = a.next // 3 points back to 2: a loop
console.log(hasCycle(a))Spot the bug
This removes every node whose value is x, but fails when the first node has value x. Which line needs changing (the fix: a dummy node)?
Exercise
Write middle(head) returning the value of the middle node (the second middle for even lengths) using fast/slow pointers. It must print 3 4.
Expected output: 3 4
class ListNode { constructor(v, n = null) { this.val = v; this.next = n } }
const fromArray = (arr) => arr.reduceRight((next, val) => new ListNode(val, next), null)
function middle(head) {
}
console.log(middle(fromArray([1, 2, 3, 4, 5])), middle(fromArray([1, 2, 3, 4, 5, 6])))Practise on real problems
Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.
Learn more from
Played 0 of 2 games
Sign in to save your progress and earn XP.