Skip to main content

21. Merge Two Sorted Lists

easyAsked at Glean

Glean tests this as a gateway to Merge K Sorted Lists — a core primitive in multi-shard search result merging where ranked result sets from different index shards must be combined in order.

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

Source citations

Public interview reports confirming this problem appears in Glean loops.

  • Glassdoor (2025-12)— Glean phone-screen reports cite merge-sorted-lists as a warm-up before moving to heap-based multi-list merges.
  • Blind (2025-09)— Glean prep threads list this as a standard easy that naturally leads into the K-list variant asked in onsites.

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]

Explanation: Compare heads, attach the smaller, advance that pointer.

Example 2

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

Explanation: Both empty — return null.

Example 3

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

Explanation: One list empty — return the other.

Approaches

1. Iterative with dummy head

Use a dummy node as the start of the merged list. Maintain a tail pointer. Compare the two list heads; attach the smaller node to tail and advance.

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

Tradeoff: O(m+n) time, O(1) space. The dummy head eliminates the special case of setting the merged list's initial head. This is the canonical iterative answer.

2. Recursive

Pick the smaller head, recurse on the remaining lists, and attach the result.

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: Elegant and concise, but uses O(m+n) stack space. Mention this risk if lists can be very long — the iterative version is safer in production.

Glean-specific tips

Connect this explicitly to Glean's architecture: 'This is essentially the merge step in a multi-shard search — each shard returns a ranked list and you merge them into one ordered result set.' Glean interviewers appreciate this framing. Always use the dummy-head pattern; it shows you've coded linked lists before and know how to avoid head-pointer edge cases.

Common mistakes

  • Not attaching the remainder after the while loop — one list runs out before the other; the remaining nodes should be appended as-is.
  • Returning dummy instead of dummy.next — the dummy node is a placeholder and must not appear in the output.
  • Creating new nodes instead of relinking existing ones — the problem says 'splicing together the nodes,' implying in-place relinking.
  • Forgetting to advance tail after each attachment — tail.next gets rewritten on the next iteration, breaking the list.

Follow-up questions

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

  • Merge K Sorted Lists (LC 23) — use a min-heap to extend this to k lists efficiently.
  • Sort List (LC 148) — sort a linked list using merge sort (requires this as a subroutine).
  • What if the lists are doubly linked?

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?

Without it, you need a special case to initialize the merged list's head pointer. With dummy, the first node attachment is identical to every subsequent one — no branching.

Can you merge in-place without the dummy?

Yes — initialize result to the smaller of the two heads before the loop. It works but requires more careful initialization code. The dummy approach is less error-prone under time pressure.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →