Week 4
Binary Search & Linked Lists
Three new twists on binary search, then linked lists from zero, with the pointer patterns (reverse, dummy node, fast and slow, gap) that solve almost every list problem.
- Binary search on a rotated array
- Binary search on the answer
- Binary search over sorted timestamps
- Reversing a linked list
- Dummy (sentinel) head node
- Fast and slow pointers
- Two pointers with a gap
- Combining patterns
This week has two halves. First, three twists on binary search: the same “halve the range” idea you met in week 3, used where the data isn’t a plain sorted array. Then linked lists, from the very beginning, and the five pointer patterns that solve most linked-list interview questions.
Binary search finds something in a sorted range by looking at the middle and throwing away the half that can’t contain the answer. Every look halves what’s left, so 1,000,000 items need only about 20 looks. That’s O(log n): double the data, and the work grows by just one extra step.
let lo = 0, hi = nums.length - 1;while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); if (nums[mid] === target) return mid; if (nums[mid] < target) lo = mid + 1; // answer is to the right else hi = mid - 1; // answer is to the left}return -1;lo, hi = 0, len(nums) - 1while lo <= hi: mid = (lo + hi) // 2 if nums[mid] == target: return mid if nums[mid] < target: lo = mid + 1 # answer is to the right else: hi = mid - 1 # answer is to the leftreturn -1If any of this is new, read the full explanation in week 3: classic binary search first. This week we keep the loop and change one thing each time: how we decide which half to keep.
An array is a row of boxes sitting side by side in memory. A linked list is different: it’s a chain of separate little objects called nodes, and each node holds two things:
val: the data (a number, for us),next: an arrow to the next node.
- head is a variable holding the first node. It’s all a function gets: “here’s the head, the rest is reachable from it”.
- next is each node’s arrow to the following node.
- null (
Nonein Python) means “nothing”. The last node’snextis null, which is how we know the list has ended. An empty list is justhead = null.
LeetCode defines this class for you in every linked-list problem (you’ll see it
in a comment above the starter code). Here it is, plus how to build 1 → 2 → 3 by hand:
ListNode
class ListNode { constructor(val = 0, next = null) { this.val = val; // the data this node carries this.next = next; // the next node, or null at the end }}// Build 1 -> 2 -> 3 by hand, starting from the backconst third = new ListNode(3);const second = new ListNode(2, third);const head = new ListNode(1, second);console.log(head.next.val); // 2class ListNode: def __init__(self, val=0, next=None): self.val = val # the data this node carries self.next = next # the next node, or None at the end# Build 1 -> 2 -> 3 by hand, starting from the backthird = ListNode(3)second = ListNode(2, third)head = ListNode(1, second)print(head.next.val) # 2A class is a blueprint for objects; new ListNode(3) / ListNode(3) creates
one node. Notice we build from the back: the 3 node must exist before the 2 node
can point at it.
With an array, nums[2] jumps straight to the third box: the computer knows the
start address and every box is the same size, so box k is at start + k. A
linked list’s nodes are scattered anywhere in memory. The only way to find the
third node is to start at head and follow two arrows. There’s no list[2].
Almost every linked-list function contains this loop: start a pointer curr at
the head, and keep moving it to curr.next until it becomes null. A pointer
here just means a variable that refers to a node. Press Play:
Walking a linked list
head = [1, 2, 3]
- head
- 1node
- curr
- 1node
- empty
- curr is here
- Already printed
All we are given is head, the first node (1). We copy it into curr so we can move curr without losing head.
Which line is running?
function printList(head) {Running now: let curr = head; while (curr !== null) { console.log(curr.val); curr = curr.next; // hop to the next node }}We copy head into curr and move curr, so head still points at the start
when we’re done.
| Array | Linked list | |
|---|---|---|
| Get the k-th item | O(1) jump | O(k) walk |
| Insert / remove at the front | O(n) (shift everything) | O(1) (change one arrow) |
| Insert / remove after a node you already hold | O(n) | O(1) |
| Find a value | O(n) | O(n) |
| Memory | one block, no extras | an extra next pointer per node |
O(1) means “a fixed amount of work, however long the list is”. O(n) means “work grows in step with the length”. Linked lists win when you rearrange a lot and lose when you jump around a lot.
Pause and think
Two lines, in this order:
nine.next = two.next(9 now points at 3),two.next = nine(2 now points at 9).
Result: 1 → 2 → 9 → 3. Only two arrows changed, whatever the list’s length:
O(1). If you did step 2 first, you’d lose your only link to 3.
LeetCode shows a list as an array: head = [1, 2, 3]. That’s just shorthand. Before
calling your function, LeetCode builds real nodes 1 → 2 → 3 and passes you the
head node; when your function returns a head, it walks the nodes and prints them as
an array again. head = [] means you receive null. In
Linked List Cycle an extra number pos says
where the tail links back to, but your function only receives head.
What it is. A sorted array that has been rotated (some numbers moved from the
front to the back, keeping their order), like [4, 5, 6, 7, 0, 1, 2]. It’s two
sorted runs with one drop between them. Normal binary search breaks, because
“nums[mid] < target, so go right” is no longer true everywhere. The fix: for any
mid, the drop is on only one side, so the other half is sorted, and we can
check whether the target fits inside it.
Pattern
Binary search on a rotated array
Use it when: the input was sorted and then rotated, values are distinct, and you need O(log n).
Signal words
- “rotated sorted array”
- “pivot”
- “sorted then shifted”
- “O(log n)”
Find the sorted half
function search(nums, target) { let lo = 0; let hi = nums.length - 1; while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); if (nums[mid] === target) return mid; if (nums[lo] <= nums[mid]) { // Left half [lo..mid] is sorted. if (nums[lo] <= target && target < nums[mid]) { hi = mid - 1; // target is inside the sorted left half } else { lo = mid + 1; // target must be on the right } } else { // Right half [mid..hi] is sorted. if (nums[mid] < target && target <= nums[hi]) { lo = mid + 1; // target is inside the sorted right half } else { hi = mid - 1; // target must be on the left } } } return -1; // the range is empty: target is not in nums}def search(nums, target): lo, hi = 0, len(nums) - 1 while lo <= hi: mid = (lo + hi) // 2 if nums[mid] == target: return mid if nums[lo] <= nums[mid]: # Left half [lo..mid] is sorted. if nums[lo] <= target < nums[mid]: hi = mid - 1 # target is inside the sorted left half else: lo = mid + 1 # target must be on the right else: # Right half [mid..hi] is sorted. if nums[mid] < target <= nums[hi]: lo = mid + 1 # target is inside the sorted right half else: hi = mid - 1 # target must be on the left return -1 # the range is empty: target is not in numsThis week: Search in Rotated Sorted Array.
What it is. Sometimes there’s no array to search. The question is “what’s the
smallest speed / capacity / size that works?” If you can write a yes/no check,
feasible(x), and its answers go no, no, …, no, yes, yes, … as x grows,
then the answer is where “no” turns into “yes”, and binary search can find that
switch over the range of possible answers.
Pattern
Binary search on the answer
Use it when: you need the minimum (or maximum) value that satisfies a condition, and the condition flips only once as the value grows.
Signal words
- “minimum speed”
- “smallest capacity”
- “within h hours / D days”
- “at least”
- “minimize the maximum”
Smallest value that works
// feasible(x) answers: "does x work?" Its answers must look like// false, false, ..., false, true, true, ..., true as x grows.function smallestThatWorks(lo, hi, feasible) { while (lo < hi) { const mid = Math.floor((lo + hi) / 2); if (feasible(mid)) { hi = mid; // mid works: the answer is mid or smaller } else { lo = mid + 1; // mid fails: the answer is bigger } } return lo;}# feasible(x) answers: "does x work?" Its answers must look like# False, False, ..., False, True, True, ..., True as x grows.def smallest_that_works(lo, hi, feasible): while lo < hi: mid = (lo + hi) // 2 if feasible(mid): hi = mid # mid works: the answer is mid or smaller else: lo = mid + 1 # mid fails: the answer is bigger return loThis week: Koko Eating Bananas.
What it is. Data arrives in time order, so a list of (timestamp, value) pairs is
already sorted by time. The question “what was the value at time t?” means
“find the latest timestamp ≤ t”. That’s a binary search that doesn’t stop at
the first match: whenever times[mid] <= t, remember mid as the best so far and
keep looking right for a later one. This is called a floor or “last ≤ t”
search. (It lands one position before the “upper bound”, which is the first
timestamp greater than t: in Python, bisect_right(times, t) − 1.)
Pattern
Binary search over sorted timestamps
Use it when: you need the latest entry at or before a time, or the largest value ≤ x, in sorted data.
Signal words
- “timestamp”
- “at or before”
- “latest version”
- “largest ≤ x”
- “strictly increasing”
Latest time ≤ t
// times is sorted. Return the index of the latest time <= t, or -1.function latestAtOrBefore(times, t) { let lo = 0; let hi = times.length - 1; let best = -1; while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); if (times[mid] <= t) { best = mid; // a candidate; maybe a later one also fits lo = mid + 1; } else { hi = mid - 1; // too late; look earlier } } return best;}# times is sorted. Return the index of the latest time <= t, or -1.def latest_at_or_before(times, t): lo, hi = 0, len(times) - 1 best = -1 while lo <= hi: mid = (lo + hi) // 2 if times[mid] <= t: best = mid # a candidate; maybe a later one also fits lo = mid + 1 else: hi = mid - 1 # too late; look earlier return best- 10
- 31
- 52
- 83
- 124
This week: Time Based Key-Value Store.
What it is. Turn 1 → 2 → 3 into 3 → 2 → 1 by flipping every arrow, in place.
We walk once with three pointers: prev (the part already reversed), curr (the node
being flipped) and next (the rest of the list, saved before we flip). It’s
also a building block: many problems reverse half a list or a section of one.
Pattern
Reversing a linked list
Use it when: you need a list, half a list, or a section of a list backwards, with O(1) extra memory.
Signal words
- “reverse”
- “reverse between left and right”
- “palindrome linked list”
- “reorder”
- “k-group”
Iterative (O(1) space)
function reverseList(head) { let prev = null; // the reversed part (empty at first) let curr = head; // the node we are flipping now while (curr !== null) { const next = curr.next; // 1. save the rest of the list curr.next = prev; // 2. flip this arrow backwards prev = curr; // 3. step prev forward curr = next; // 4. step curr forward } return prev; // the old tail is the new head}def reverse_list(head): prev = None # the reversed part (empty at first) curr = head # the node we are flipping now while curr is not None: nxt = curr.next # 1. save the rest of the list curr.next = prev # 2. flip this arrow backwards prev = curr # 3. step prev forward curr = nxt # 4. step curr forward return prev # the old tail is the new headRecursive (O(n) stack space)
function reverseList(head) { if (head === null || head.next === null) { return head; // 0 or 1 node: already reversed } const newHead = reverseList(head.next); // reverse everything after head head.next.next = head; // the node after head points back at head head.next = null; // head is now the tail of the reversed part return newHead;}def reverse_list(head): if head is None or head.next is None: return head # 0 or 1 node: already reversed new_head = reverse_list(head.next) # reverse everything after head head.next.next = head # the node after head points back at head head.next = None # head is now the tail of the reversed part return new_headThe recursive version says: “reverse everything after head (trust the call),
then make the node after head point back at head, and cut head.next.” Here’s
the iterative pointer dance, step by step:
Iterative: prev, curr, next
head = [1, 2, 3, 4]
- prev
- null
- curr
- 1node
- curr (being flipped)
- next (saved)
- Already reversed (prev's list)
- Arrow just flipped
- Reversed list
We will flip every arrow so it points backwards. prev holds the part we have already reversed. At the start that part is empty, so prev = null.
Which line is running?
function reverseList(head) {Running now: let prev = null; // the reversed part (empty at first) let curr = head; // the node we are flipping now while (curr !== null) { const next = curr.next; // 1. save the rest of the list curr.next = prev; // 2. flip this arrow backwards prev = curr; // 3. step prev forward curr = next; // 4. step curr forward } return prev; // the old tail is the new head}This week: Reverse Linked List, and phase 2 of Reorder List.
What it is. A fake node we create in front of the real head:
dummy = new ListNode(0, head). Its value is never used. It means every real
node, even the head, has a node before it, so “insert at the front” and “remove
the head” stop being special cases. At the end, the real head is dummy.next.
Pattern
Dummy (sentinel) head node
Use it when: you build a new list node by node, or may delete or replace the head.
Signal words
- “merge lists”
- “remove nodes”
- “delete the head”
- “partition list”
- “build the result list”
Remove every node with a given value
// Remove every node whose value is val (LeetCode 203).function removeElements(head, val) { const dummy = new ListNode(0, head); // a node BEFORE head let prev = dummy; while (prev.next !== null) { if (prev.next.val === val) { prev.next = prev.next.next; // unlink it; works for the head too } else { prev = prev.next; } } return dummy.next; // the real head (it may have changed)}# Remove every node whose value is val (LeetCode 203).def remove_elements(head, val): dummy = ListNode(0, head) # a node BEFORE head prev = dummy while prev.next is not None: if prev.next.val == val: prev.next = prev.next.next # unlink it; works for the head too else: prev = prev.next return dummy.next # the real head (it may have changed)This week: Merge Two Sorted Lists and Remove Nth Node From End of List.
What it is. Two pointers walk the same list at different speeds: slow one node
per step, fast two. Two classic uses:
- Find the middle: when
fastreaches the end,slowhas gone exactly half as far. - Detect a cycle (Floyd’s algorithm): if the list loops,
fastcan never reach the end, and inside the loop it gains one node per step onslow, so the gap between them shrinks 3, 2, 1, 0 and they meet.
Pattern
Fast and slow pointers
Use it when: you need the middle of a list, or to detect (or locate) a loop, in O(1) memory.
Signal words
- “middle of the linked list”
- “cycle”
- “loop”
- “O(1) space”
- “duplicate number”
Find the middle
function middleNode(head) { let slow = head; let fast = head; while (fast !== null && fast.next !== null) { slow = slow.next; // 1 step fast = fast.next.next; // 2 steps } return slow; // with an even length: the second of the two middles}def middle_node(head): slow = head fast = head while fast is not None and fast.next is not None: slow = slow.next # 1 step fast = fast.next.next # 2 steps return slow # with an even length: the second of the two middlesFast and slow pointers find the middle
head = [1, 2, 3, 4, 5]
- slow
- 1node
- fast
- 1node
- slow
- fast
- Middle
slow and fast both start at the head.
Which line is running?
function middleNode(head) { let slow = head;Running now: let fast = head; while (fast !== null && fast.next !== null) { slow = slow.next; // 1 step fast = fast.next.next; // 2 steps } return slow; // with an even length: the second of the two middles}This week: Linked List Cycle, and phase 1 of Reorder List.
What it is. To find something measured from the end of a one-way list in a
single pass: move a lead pointer n nodes ahead, then move lead and trail
together. The gap stays n, so when lead falls off the end, trail is n nodes
from the end.
Pattern
Two pointers with a gap
Use it when: you need the k-th node from the end, or to cut a list k nodes from the end, in one pass.
Signal words
- “n-th from the end”
- “k-th to last”
- “one pass”
- “rotate list”
N-th node from the end
// Return the n-th node from the end (n = 1 is the last node).function nthFromEnd(head, n) { let lead = head; for (let i = 0; i < n; i++) { lead = lead.next; // lead gets n steps ahead } let trail = head; while (lead !== null) { lead = lead.next; trail = trail.next; // same speed: the gap stays n } return trail;}# Return the n-th node from the end (n = 1 is the last node).def nth_from_end(head, n): lead = head for _ in range(n): lead = lead.next # lead gets n steps ahead trail = head while lead is not None: lead = lead.next trail = trail.next # same speed: the gap stays n return trailThis week: Remove Nth Node From End of List.
What it is. Most medium list problems are two or three of the patterns above,
run one after another. Reorder List wants L0 → Ln → L1 → Ln-1 → …: the front
half in order, interleaved with the back half reversed. So:
- Find the middle (fast and slow),
- Reverse the second half (prev / curr / next),
- Merge alternately (two pointers, one per half).
Pattern
Combining patterns
Use it when: the answer mixes the front and back of a list, or needs two passes of different kinds, in O(1) space.
Signal words
- “reorder”
- “L0 → Ln → L1”
- “palindrome linked list”
- “in place”
- “O(1) extra space”
Reorder List: middle, reverse, merge
function reorderList(head) { if (head === null || head.next === null) return; // Phase 1: find the middle let slow = head; let fast = head; while (fast.next !== null && fast.next.next !== null) { slow = slow.next; fast = fast.next.next; } // Phase 2: reverse the second half let prev = null; let curr = slow.next; slow.next = null; // cut the list in two while (curr !== null) { const next = curr.next; curr.next = prev; prev = curr; curr = next; } // Phase 3: merge the two halves, alternating let first = head; let second = prev; while (second !== null) { const tmp1 = first.next; const tmp2 = second.next; first.next = second; second.next = tmp1; first = tmp1; second = tmp2; }}def reorder_list(head): if head is None or head.next is None: return # Phase 1: find the middle slow, fast = head, head while fast.next is not None and fast.next.next is not None: slow = slow.next fast = fast.next.next # Phase 2: reverse the second half prev, curr = None, slow.next slow.next = None # cut the list in two while curr is not None: nxt = curr.next curr.next = prev prev = curr curr = nxt # Phase 3: merge the two halves, alternating first, second = head, prev while second is not None: tmp1, tmp2 = first.next, second.next first.next = second second.next = tmp1 first, second = tmp1, tmp2This week: Reorder List.
Linked-list bugs are almost always one of these. Run through the list before you press Submit.
- Null checks before every
.next. Beforex.next, be surexisn’t null. Beforex.next.next, be surex.nextisn’t null too (fast && fast.next). - Save
nextbefore rewiring. Any time you overwritenode.next, first store the old value if you still need the rest of the list. - Order of assignments. When inserting: link the new node to the rest first,
then link the previous node to the new one. When stepping:
prev = currbeforecurr = next. - Use a dummy node whenever the head might change or the result starts empty.
- Return the right head:
prevafter reversing,dummy.nextwith a dummy, never a stalehead. - Cut what should be separate (
slow.next = null), or you’ll create a cycle. - Test the tiny cases: empty list, one node, two nodes, and odd vs even length.
A suggested order, each step adding one idea:
- Reverse Linked List (Easy). Start here: it
teaches the core skill of the week, rewiring
nextsafely, and the prev / curr / next dance you’ll reuse. - Merge Two Sorted Lists (Easy). Adds the
dummy node and a
tailpointer for building a list. - Linked List Cycle (Easy). Adds fast and slow pointers, and a neat proof of why they work.
- Remove Nth Node From End of List (Medium). Pointers with a fixed gap, plus the dummy node again for removing the head.
- Reorder List (Medium). The finale for lists: it combines fast/slow, reversal and merging. If you did 1–4, every piece is familiar.
- Search in Rotated Sorted Array (Medium). Switch to binary search. After the week 3 recap, this changes only the “which half?” rule.
- Time Based Key-Value Store (Medium). Binary search for “latest ≤ t” inside a small design problem (a class).
- Koko Eating Bananas (Medium). The biggest mental leap: binary search over answers instead of an array. Save it for last so the binary search loop itself feels automatic.
If you prefer to keep the binary search fresh from week 3, do 6–8 first; the two halves of the week don’t depend on each other.
This week's problems
0 of 8 done
A sorted array was turned like a dial. Find a target's index in O(log n) by working out which half is still sorted.
Find the slowest eating speed that still finishes every pile of bananas in h hours, by binary searching over the speeds.
Build a key-value store that remembers every version of a value, and answers "what was the value at time t?" with binary search.
Turn 1 → 2 → 3 into 3 → 2 → 1 by flipping every arrow, using three pointers (or recursion).
Zip two sorted linked lists into one sorted list by always taking the smaller front node, with a dummy node to start from.
Decide whether a linked list loops back on itself, using a slow and a fast pointer (or a set of visited nodes).
Delete the n-th node counted from the end in one pass, using two pointers n apart and a dummy node in front of the head.
Rearrange a list into first, last, second, second-to-last, ... in place, by finding the middle, reversing the second half, and zipping the halves together.