21. Merge Two Sorted Lists

Q: Why use a dummy head?

It eliminates the special case of initializing the head of the merged list. Without it, you need an if/else before the loop to set the first node.

Q: Is it safe to reuse the original nodes?

Yes — the problem says 'splicing together the nodes', so modifying next pointers on existing nodes is the intended approach.

Q: What if both lists are empty?

Both null-checks in the loop's condition fire immediately; tail.next = null; dummy.next = null; returns null. Correct.

easyAsked at Anduril

Merge two sorted linked lists into one sorted list. Anduril uses this to test pointer discipline and the ability to reason about invariants — skills that transfer to merging ordered sensor-event streams from multiple autonomous subsystems without breaking temporal ordering.

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

Source citations

Public interview reports confirming this problem appears in Anduril loops.

Glassdoor (2025-12)— Anduril SWE phone-screen prep reports cite merge-sorted-lists as a linked-list pointer discipline check.
Blind (2025-09)— Multiple Anduril interview threads list this problem for new-grad and mid-level roles.

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 are merged by value in non-decreasing order.

Example 2

Input

list1 = [], list2 = []

Output

[]

Explanation: Both lists 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 head node to simplify the merge. Advance a tail pointer through whichever list has the smaller current value.

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;
  }
  // attach the remainder of the non-exhausted list
  tail.next = list1 !== null ? list1 : list2;
  return dummy.next;
}

Tradeoff: O(1) extra space (just the dummy node). Dummy head eliminates the special-case of building the first node. This is the cleanest and most preferred approach at Anduril.

2. Recursive

Choose the smaller head, attach the result of merging the rest recursively.

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 space. In embedded contexts, Anduril engineers flag call-stack depth — prefer iterative when lists can be long.

Anduril-specific tips

Use a dummy head and articulate why: 'A dummy head lets me avoid special-casing the first node — the merge logic is uniform from start to finish.' Anduril engineers value clean invariants. After the while loop, attach the remainder directly — you don't need to continue iterating because both input lists are already sorted. Mention the O(1) space benefit of the iterative approach versus recursion.

Common mistakes

Forgetting to attach the non-exhausted tail — when one list runs out, the other's remaining nodes should be appended directly.
Returning dummy instead of dummy.next — the dummy node is a sentinel, not part of the answer.
Not advancing tail after each attachment — tail.next is set but tail itself never moves, causing an infinite loop.
Modifying node values instead of relinking — merge by relinking pointers, not by copying values into a new list.

Follow-up questions

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

Merge K sorted lists (LC 23) — use a min-heap or divide-and-conquer.
How would you merge two sorted circular doubly-linked lists?
What if the lists contain duplicates and you want to keep only unique values?

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 initializing the head of the merged list. Without it, you need an if/else before the loop to set the first node.

Is it safe to reuse the original nodes?

Yes — the problem says 'splicing together the nodes', so modifying next pointers on existing nodes is the intended approach.

What if both lists are empty?

Both null-checks in the loop's condition fire immediately; tail.next = null; dummy.next = null; returns null. Correct.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →