Skip to main content

3. Merge Two Sorted Lists

easyAsked at Coinbase

Splice two sorted linked lists into one sorted list. Coinbase uses this to test pointer manipulation — a common building block when merging streams of order-book updates from different feeds.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Coinbase loops.

  • Glassdoor (2026-Q1)— Coinbase L3/L4 backend phone screen.
  • Blind (2025-09)— Reported as a warm-up before order-book-merge follow-up.

Problem

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

Constraints

  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both list1 and list2 are sorted in non-decreasing order.

Examples

Example 1

Input
list1 = [1,2,4], list2 = [1,3,4]
Output
[1,1,2,3,4,4]

Example 2

Input
list1 = [], list2 = []
Output
[]

Example 3

Input
list1 = [], list2 = [0]
Output
[0]

Approaches

1. Build a new list by copying values

Walk both lists, copy smaller value into a new list each step.

Time
O(n+m)
Space
O(n+m)
function mergeTwoLists(l1, l2) {
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (l1 && l2) {
    tail.next = { val: Math.min(l1.val, l2.val), next: null };
    if (l1.val <= l2.val) l1 = l1.next; else l2 = l2.next;
    tail = tail.next;
  }
  return dummy.next;
}

Tradeoff: Allocates new nodes. Works but wastes memory and ignores the 'splice nodes' hint.

2. In-place splicing with dummy head

Use a dummy head and a tail pointer. Walk both lists, attaching the smaller current node and advancing only that list. After the loop, attach whatever remains.

Time
O(n+m)
Space
O(1)
function mergeTwoLists(l1, l2) {
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
    else { tail.next = l2; l2 = l2.next; }
    tail = tail.next;
  }
  tail.next = l1 || l2;
  return dummy.next;
}

Tradeoff: Splices existing nodes — O(1) extra space. The dummy-head pattern simplifies the head-edge case.

Coinbase-specific tips

Coinbase often follows with 'merge K sorted feeds of trades' so explicitly call out that this generalizes to a min-heap of K lists. Mention how you'd handle ties deterministically — order-book replay must produce the same output every time, which means a stable comparator that breaks ties by feed ID or sequence number.

Common mistakes

  • Forgetting to attach the leftover tail (l1 || l2) — last few nodes get dropped.
  • Using strict less-than instead of <= — duplicates may end up in non-deterministic order.
  • Recursive solution without thinking about stack depth — fine for 50 nodes, not for streams.

Follow-up questions

An interviewer at Coinbase may pivot to one of these next:

  • Generalize to merge K sorted lists (min-heap).
  • Merge in-place when both lists share the same underlying array index.
  • Streaming: lists are infinite and arrive over time — design a merger.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why <=, not <?

Use <= so the merge is stable: nodes from list1 keep their relative order with equal-valued nodes from list2. Stability matters when ordering by price but breaking ties by arrival time.

When would you go recursive instead?

Only when the inputs are bounded and you want fewer lines. Recursive merges blow stack for inputs > ~10k, which is common for real order books.

Practice these live with InterviewChamp.AI

Drill Merge Two Sorted Lists and other Coinbase interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →