Skip to main content

21. Merge Two Sorted Lists

easyAsked at Bloomberg

Splice two ascending linked lists into one sorted list. Bloomberg uses this to test pointer hygiene and the dummy-head trick — they want clean code with no special-case branching for the empty-list edge.

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

Source citations

Public interview reports confirming this problem appears in Bloomberg loops.

  • Glassdoor (2026-Q1)— Bloomberg phone-screen reports cite Merge Two Sorted Lists as a recurring pairing question with Reverse Linked List.
  • Blind (2025-12)— Bloomberg SWE new-grad reports list it as the second linked-list question in the onsite.

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. Iterative with dummy head

Walk both lists with a tail pointer; attach the smaller node each step. Dummy head eliminates the 'who's first?' branch.

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

Tradeoff: Splices in-place — O(1) extra memory. The dummy node makes the code branch-free at the front. Bloomberg interviewers grade specifically on this pattern.

2. Recursive

Pick the smaller head, recurse on the rest, return.

Time
O(n + m)
Space
O(n + m)
function mergeTwoListsRecursive(list1, list2) {
  if (!list1) return list2;
  if (!list2) return list1;
  if (list1.val <= list2.val) {
    list1.next = mergeTwoListsRecursive(list1.next, list2);
    return list1;
  } else {
    list2.next = mergeTwoListsRecursive(list1, list2.next);
    return list2;
  }
}

Tradeoff: Compact and elegant but O(n + m) stack space. Not ideal for very long lists — mention if the interviewer probes.

Bloomberg-specific tips

Bloomberg interviewers specifically check whether you use a DUMMY HEAD. Skipping it forces an if-block at the start to decide which list owns the head, which is uglier and bug-prone. State 'I'll use a dummy node to make the head case branchless' before coding.

Common mistakes

  • Forgetting to append the tail when one list runs out.
  • Creating new nodes instead of splicing existing ones (uses unnecessary O(n) space).
  • Off-by-one when comparing values — use <= to maintain stable order for duplicates.

Follow-up questions

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

  • Merge k Sorted Lists (LC 23) — heap or divide-and-conquer merge.
  • Sort List (LC 148) — bottom-up merge sort on a linked list.
  • Add Two Numbers (LC 2) — similar dummy-head pattern for addition with carry.

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 branch that decides 'which of list1/list2 owns the merged head?' so the loop is uniform. The dummy is local — never returned.

Stable or unstable?

Use <= (not <) so equal values keep list1's ordering relative to list2's — that's the stable merge.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →