Skip to main content

21. Merge Two Sorted Lists

easyAsked at Elastic

Merge two sorted linked lists into one sorted list. Elastic interviews this because it is the atomic merge step in merge sort — and merge sort is the exact mechanism Elasticsearch uses when combining sorted posting lists during multi-term query execution.

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

Source citations

Public interview reports confirming this problem appears in Elastic loops.

  • Glassdoor (2025-12)— Elastic SWE interviews frequently include sorted-merge problems as a lead-in to the harder merge-K-sorted-lists question.
  • Blind (2025-09)— Elastic threads note two-way merge is a building block question before discussing multi-shard result merging in the system design round.

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 each list 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]

Explanation: Nodes are interleaved by value in sorted order.

Example 2

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

Explanation: Both lists empty, result is empty.

Example 3

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

Explanation: One empty list, result is the other list.

Approaches

1. Iterative with dummy head

Use a dummy node to simplify head selection. Walk both lists simultaneously, always appending the smaller current node to the result. Append the remaining non-null list at the end.

Time
O(m + n)
Space
O(1)
function mergeTwoLists(list1, list2) {
  const dummy = { val: -1, next: null };
  let curr = dummy;
  while (list1 !== null && list2 !== null) {
    if (list1.val <= list2.val) {
      curr.next = list1;
      list1 = list1.next;
    } else {
      curr.next = list2;
      list2 = list2.next;
    }
    curr = curr.next;
  }
  curr.next = list1 !== null ? list1 : list2;
  return dummy.next;
}

Tradeoff: O(m+n) time, O(1) space — optimal. The dummy head eliminates the edge case of choosing the initial head node.

2. Recursive

At each step, choose the smaller head and recursively merge the rest.

Time
O(m + n)
Space
O(m + n) call stack
function mergeTwoLists(list1, list2) {
  if (list1 === null) return list2;
  if (list2 === null) return list1;
  if (list1.val <= list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  } else {
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
  }
}

Tradeoff: Clean and readable, but O(m+n) stack depth — can overflow for very long lists. Good for explaining the logic; prefer iterative in production.

Elastic-specific tips

Elastic interviewers expect you to immediately escalate to Merge K Sorted Lists after solving this. Prepare your answer: 'The two-way merge is the building block. For K lists, I would use a min-heap of size K — O(n log K) total, where n is total nodes.' This shows you understand how Elasticsearch merges results from K shards using a priority queue.

Common mistakes

  • Not handling empty input lists — always check list1 === null and list2 === null as base cases.
  • Appending both tails instead of just one — after the while loop, exactly one list is exhausted; append the other.
  • Forgetting to advance curr after each append — curr.next = node AND curr = curr.next must both execute.
  • Using <= vs < when values are equal — either works; just be consistent and explain your choice.

Follow-up questions

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

  • Merge K Sorted Lists (LC 23) — use a min-heap (priority queue) for O(n log K).
  • Sort List (LC 148) — sort a linked list using merge sort; uses this as a subroutine.
  • How does Elasticsearch merge sorted posting lists from different shards?

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 use a dummy head node?

Without it, you need special logic to choose the initial head of the merged list. The dummy node makes the first iteration identical to all subsequent iterations.

What if the lists have different lengths?

The while loop exits when either list is exhausted. The remaining nodes of the longer list are already sorted, so you can append them directly without further comparisons.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →