Skip to main content

3. Merge Two Sorted Lists

easyAsked at Snowflake

Merge two sorted linked lists into one sorted list. Snowflake asks this because it's the core primitive in a sort-merge join — and they want to see whether you handle the dummy-head pattern cleanly.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2026-Q1)— Snowflake storage-team screens reference this as join-primitive warm-up.
  • LeetCode Discuss (2025-11)— Asked at Snowflake new-grad onsite paired with external-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. Collect into array, sort, rebuild

Walk both lists into an array, sort, build new linked list.

Time
O((n+m) log(n+m))
Space
O(n+m)
function mergeTwoLists(l1, l2) {
  const vals = [];
  while (l1) { vals.push(l1.val); l1 = l1.next; }
  while (l2) { vals.push(l2.val); l2 = l2.next; }
  vals.sort((a, b) => a - b);
  const dummy = { val: 0, next: null };
  let curr = dummy;
  for (const v of vals) { curr.next = { val: v, next: null }; curr = curr.next; }
  return dummy.next;
}

Tradeoff: Throws away the fact that inputs are already sorted. A sort-merge join that does this is fired.

2. Two-pointer splice (optimal)

Use a dummy head. Walk both lists with two pointers; at each step splice the smaller node onto the tail. When one list is exhausted, attach the other.

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: Linear, in-place (no new nodes). Exactly the merge step of a sort-merge join.

Snowflake-specific tips

Snowflake interviewers want the dummy-head pattern — it eliminates the 'is this the first node?' branch that trips up most candidates. Bonus signal: extend to k-way merge (LC 23) and explain why a min-heap of size k is the right data structure for external sort-merge in Snowflake's spill-to-S3 sort.

Common mistakes

  • Not using a dummy head — leads to special-case code for the first node.
  • Forgetting to attach the remaining list (l1 or l2) after one is exhausted.
  • Allocating new nodes instead of splicing existing ones, which doubles memory.

Follow-up questions

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

  • Merge k sorted lists (LC 23) — extend to a min-heap.
  • Merge two sorted arrays in-place (LC 88).
  • External merge: what if the two lists don't fit in RAM?

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 dummy head?

It removes the special case for the first inserted node. Without it, you have to check 'do I update head, or do I splice onto the tail?' on every iteration.

When would Snowflake choose sort-merge over hash join?

When inputs are already sorted (e.g., from clustered storage), when join keys have skew that breaks hash partitioning, or when memory is tight and hash table spilling would be more expensive than a streaming merge.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →