intermediate

Review: the merge that drops the tail

This is recall. The code looks finished and is wrong. Find the defect and fix it. You are graded on tests you cannot see.

The nightly job merges two sorted feeds of roughly equal size, with a helper written around a dummy head and a single loop. Its tests pass, the dashboards look right.

interface ListNode {
  value: number
  next?: ListNode
}

/**
 * Merges two ascending lists into one ascending list, reusing the input
 * nodes. On equal values the node from `a` comes first.
 */
export function mergeSorted(
  a: ListNode | undefined,
  b: ListNode | undefined
): ListNode | undefined {
  const head: ListNode = { value: Number.NaN }
  let tail = head

  let left = a
  let right = b
  while (left !== undefined && right !== undefined) {
    if (left.value <= right.value) {
      tail.next = left
      left = left.next
    } else {
      tail.next = right
      right = right.next
    }
    tail = tail.next as ListNode
  }

  return head.next
}

review — find the defectCtrl+↵ submits · Ctrl+Shift+↵ runsstarter code