Skip to main content

3. Merge Two Sorted Lists

easyAsked at Databricks

Merge two sorted linked lists into one sorted list. Databricks uses this as a launchpad to the real question they care about: how does this generalize to merging K sorted partitions during a shuffle?

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

Source citations

Public interview reports confirming this problem appears in Databricks loops.

  • Glassdoor (2025-12)— Databricks shuffle-engineer phone screen; merge is the warm-up, K-way merge is the real question.
  • Reddit r/cscareerquestions (2026-Q1)— Reported as the bridge between LC easy and 'how does Spark sort 1TB?'

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

Approaches

1. Collect all, sort, rebuild

Dump both into an array, sort it, build a new list.

Time
O((n+m) log(n+m))
Space
O(n+m)
function mergeTwoLists(a, b) {
  const arr = [];
  for (let p = a; p; p = p.next) arr.push(p.val);
  for (let p = b; p; p = p.next) arr.push(p.val);
  arr.sort((x, y) => x - y);
  const head = { next: null }; let t = head;
  for (const v of arr) { t.next = { val: v, next: null }; t = t.next; }
  return head.next;
}

Tradeoff: Throws away the sorted-input invariant. Never ship at Databricks where they grade on respecting structure.

2. Two-pointer splice with sentinel

Walk both lists with two pointers, splicing the smaller into a new tail. A sentinel head simplifies the first-node case.

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

Tradeoff: Linear, in-place splicing reuses existing nodes. Sentinel removes the head-edge-case branch.

Databricks-specific tips

Databricks loves to follow this with 'now merge K sorted partitions from a shuffle' — be ready to talk about min-heap K-way merge, external merge sort spilling to disk, and how Spark's sort-merge join uses exactly this primitive. The bonus signal is articulating why a heap (not pairwise merging) wins when K is large.

Common mistakes

  • Creating new nodes instead of splicing — wastes memory and signals you don't trust pointer manipulation.
  • Forgetting to attach the remaining tail (a || b) after one list runs out.
  • Using < instead of <= and breaking stability on equal keys (matters when this becomes the building block for stable sort-merge join).

Follow-up questions

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

  • Merge K sorted lists — heap of K heads.
  • External sort: K-way merge of files that don't fit in RAM.
  • Stable merge for sort-merge join: how do ties affect downstream aggregation?

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 a sentinel/dummy head?

Without it you'd branch on 'is this the first node?' inside the loop. The sentinel makes every iteration identical and you return dummy.next at the end.

Why <= not <?

Stability. With <=, if a.val == b.val you take from list a first, preserving the relative order of equal keys. Sort-merge join in Spark depends on this.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →