21. Merge Two Sorted Lists

Q: Why use a dummy head?

It eliminates the special case of setting the head of the merged list. Without it, you need an if-block before the loop to initialize the head pointer — messy and error-prone.

Q: Can this be done in O(1) space without recursion?

Yes — the iterative approach uses O(1) extra space (just the dummy node and tail pointer). No new list nodes are allocated.

Q: What if both lists contain duplicates?

No issue — the <= comparison means equal values from list1 are placed before list2's equal values, maintaining stability.

easyAsked at Citadel

Merging two sorted lists is the inner loop of merge sort and a primitive in time-series data fusion. At Citadel, this maps directly to merging two ordered streams of market events from separate exchanges. Interviewers watch whether you use a dummy head node and whether you handle leftover tails cleanly.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in Citadel loops.

Glassdoor (2025-11)— Citadel SWE candidates mention linked-list merge problems as reliable fixtures in first-round technical screens.
Blind (2025-08)— Merge Two Sorted Lists cited alongside Merge K Sorted Lists in Citadel interview prep threads as a required baseline.

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: Nodes interleaved by value in sorted order.

Example 2

Input

list1 = [], list2 = []

Output

[]

Explanation: Both empty — return null.

Example 3

Input

list1 = [], list2 = [0]

Output

[0]

Explanation: One empty list — return the other.

Approaches

1. Iterative with dummy head

Use a dummy head node to avoid special-casing the head. Advance a tail pointer and attach the smaller node at each step. Attach 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 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;
  }
  // attach remaining nodes
  tail.next = list1 !== null ? list1 : list2;
  return dummy.next;
}

Tradeoff: O(m+n) time, O(1) space. In-place pointer rewiring — no new nodes allocated. The dummy head eliminates null checks for the initial head assignment. This is the canonical answer.

2. Recursive

Choose the smaller head recursively. The rest of the list is built by the recursive call.

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 but O(m+n) stack frames. For very long lists this risks stack overflow. Mention this tradeoff explicitly — Citadel cares about production-grade robustness.

Citadel-specific tips

Frame the problem in market terms: 'I'm merging two time-ordered event queues from two different exchanges. I always consume the earlier-timestamped event, keeping the merged output in chronological order.' This framing resonates strongly in a Citadel interview. Also note that the iterative version maps directly to a hardware merge unit in FPGA-based trading systems — two sorted input streams, one sorted output, combinatorial logic.

Common mistakes

Not using a dummy head and then writing special-case logic for the first node — this is error-prone and harder to read.
Forgetting tail.next = remaining list at the end — the leftover nodes are already sorted and can be attached in O(1).
Using a loop condition of list1 !== null || list2 !== null and then requiring null checks inside — harder to reason about than the && version with a tail attachment.
Allocating new nodes instead of rewiring existing ones — wastes memory and is unnecessary.

Follow-up questions

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

Merge K Sorted Lists (LC 23) — use a min-heap for O(n log k) efficiency.
Sort List (LC 148) — merge sort a linked list using this as the merge step.
How would you merge two sorted arrays in place without extra memory?

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?

It eliminates the special case of setting the head of the merged list. Without it, you need an if-block before the loop to initialize the head pointer — messy and error-prone.

Can this be done in O(1) space without recursion?

Yes — the iterative approach uses O(1) extra space (just the dummy node and tail pointer). No new list nodes are allocated.

What if both lists contain duplicates?

No issue — the <= comparison means equal values from list1 are placed before list2's equal values, maintaining stability.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →