Skip to content
16-Week DSA Roadmap

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: a quick recap

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 -1

If 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.

What is a linked list?

Nodes: a train of carriages

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.
123
The list [1, 2, 3]: three nodes, each pointing to the next. The last one points to null: the end.

head, next and null

  • 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 (None in Python) means “nothing”. The last node’s next is null, which is how we know the list has ended. An empty list is just head = null.

The ListNode class

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); // 2
class 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)  # 2

A 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.

No index access

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].

Array: boxes side by side10@30020@30430@30840@312box k lives at 300 + 4 × k,so nums[3] is one jump: O(1)Linked list: nodes anywhere, each knows the next one's address10@840@51220@176@84030@960@17640null@960To reach 40 we must start at 10 and follow 3 arrows: O(n).
Same four values, two layouts. The array can compute where any box is; the list must follow the chain from the start.

Walking a list (traversal)

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]

123
variables
head
1node
curr
1node
printed
  1. 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.

Step 1 / 8

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.

Arrays vs linked lists

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

You hold a pointer to the node with value 2 in 1 → 2 → 3. How do you insert a new node 9 right after it? How many arrows change?

How LeetCode writes linked lists

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.

Pattern: Binary search on a rotated array

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 nums
40516273041526the dropmid
mid = 3 (value 7). nums[lo] = 4 ≤ 7, so the shaded left half is sorted and can only hold values 4..7. A target of 0 must be on the right.

This week: Search in Rotated Sorted Array.

Pattern: Binary search on the answer

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 lo
speed k (bananas per hour)
1234567891011lo=4hi=6mid=5
Koko Eating Bananas, piles [3, 6, 7, 11], h = 8: speeds 1..11 are the answer space. After testing 6 (works, green) and 3 (too slow, red), only 4..6 is left.

This week: Koko Eating Bananas.

Pattern: Binary search over sorted timestamps

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
times
  1. 10
  2. 31
  3. 52
  4. 83
  5. 124
times = [1, 3, 5, 8, 12], t = 9. Every time up to 8 is ≤ 9 (candidates), 12 is too late. The search keeps the LAST candidate: index 3.

This week: Time Based Key-Value Store.

Pattern: Reversing a linked list

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 head

Recursive (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_head

The 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]

1234
variables
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.

Step 1 / 19

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.

Pattern: Dummy (sentinel) head node

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)
D123
Removing the head (1) from 1 → 2 → 3: with a dummy D in front, it's the usual 'point past it' move, and dummy.next is the new head (2).

This week: Merge Two Sorted Lists and Remove Nth Node From End of List.

Pattern: Fast and slow pointers

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 fast reaches the end, slow has gone exactly half as far.
  • Detect a cycle (Floyd’s algorithm): if the list loops, fast can never reach the end, and inside the loop it gains one node per step on slow, 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 middles

Fast and slow pointers find the middle

head = [1, 2, 3, 4, 5]

12345
variables
slow
1node
fast
1node
  • slow
  • fast
  • Middle

slow and fast both start at the head.

Step 1 / 4

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}
THgap 3startTHgap 2after turn 1THgap 1after turn 2✓gap 0after turn 3they meet
Inside a loop of 6 nodes, the hare (H) closes the gap on the tortoise (T) by one node per turn until they meet.

This week: Linked List Cycle, and phase 1 of Reorder List.

Pattern: Two pointers with a gap

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 trail
12345
The template above with n = 2 on [1, 2, 3, 4, 5], at the moment it returns. lead went 2 nodes ahead (to 3), then lead and trail moved together until lead fell off the end: lead is now null, just past 5. trail is on 4, the 2nd node from the end. (Remove Nth Node uses a variant: it starts both from a dummy node and stops one node earlier, so it lands just before 4, ready to unlink it.)

This week: Remove Nth Node From End of List.

Pattern: Combining patterns

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:

  1. Find the middle (fast and slow),
  2. Reverse the second half (prev / curr / next),
  3. 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, tmp2
1. find the middle
12345
2. cut, reverse the second half
12354
3. merge alternately
15243
The three phases on [1, 2, 3, 4, 5]: find the middle (3), cut and reverse the second half (5 → 4), then zip: 1 → 5 → 2 → 4 → 3.

This week: Reorder List.

Pointer safety checklist

Linked-list bugs are almost always one of these. Run through the list before you press Submit.

  1. Null checks before every .next. Before x.next, be sure x isn’t null. Before x.next.next, be sure x.next isn’t null too (fast && fast.next).
  2. Save next before rewiring. Any time you overwrite node.next, first store the old value if you still need the rest of the list.
  3. 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 = curr before curr = next.
  4. Use a dummy node whenever the head might change or the result starts empty.
  5. Return the right head: prev after reversing, dummy.next with a dummy, never a stale head.
  6. Cut what should be separate (slow.next = null), or you’ll create a cycle.
  7. Test the tiny cases: empty list, one node, two nodes, and odd vs even length.

Problem roadmap

A suggested order, each step adding one idea:

  1. Reverse Linked List (Easy). Start here: it teaches the core skill of the week, rewiring next safely, and the prev / curr / next dance you’ll reuse.
  2. Merge Two Sorted Lists (Easy). Adds the dummy node and a tail pointer for building a list.
  3. Linked List Cycle (Easy). Adds fast and slow pointers, and a neat proof of why they work.
  4. Remove Nth Node From End of List (Medium). Pointers with a fixed gap, plus the dummy node again for removing the head.
  5. Reorder List (Medium). The finale for lists: it combines fast/slow, reversal and merging. If you did 1–4, every piece is familiar.
  6. Search in Rotated Sorted Array (Medium). Switch to binary search. After the week 3 recap, this changes only the “which half?” rule.
  7. Time Based Key-Value Store (Medium). Binary search for “latest ≤ t” inside a small design problem (a class).
  8. 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

  1. 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.

  2. 2. #875Koko Eating BananasMedium

    Find the slowest eating speed that still finishes every pile of bananas in h hours, by binary searching over the speeds.

  3. Build a key-value store that remembers every version of a value, and answers "what was the value at time t?" with binary search.

  4. Turn 1 → 2 → 3 into 3 → 2 → 1 by flipping every arrow, using three pointers (or recursion).

  5. Zip two sorted linked lists into one sorted list by always taking the smaller front node, with a dummy node to start from.

  6. Decide whether a linked list loops back on itself, using a slow and a fast pointer (or a set of visited nodes).

  7. 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.

  8. 8. #143Reorder ListMedium

    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.