21. Merge Two Sorted Lists

Q: Why use a dummy head instead of special-casing the first node?

A dummy head means tail.next always has somewhere to point. Without it you need separate logic to establish the result head, which is error-prone and harder to read.

Q: Is it OK to reuse the original nodes rather than creating new ones?

Yes — the problem says to splice together the original nodes, which is more efficient than allocating new nodes.

Q: What if one list is much longer than the other?

The algorithm handles this naturally — after the while loop exits you attach the remainder of the longer list in O(1) by pointing tail.next at the remaining head.

easyAsked at Gusto

Merge two sorted linked lists into one sorted list. Gusto uses this to test linked-list pointer discipline and to see if you reach for a dummy head node — the single trick that eliminates all the edge-case noise.

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

Source citations

Public interview reports confirming this problem appears in Gusto loops.

Glassdoor (2025-11)— Cited in Gusto SWE phone-screen reports as a linked-list fundamentals check with a follow-up on merging k lists.
Blind (2025-09)— Gusto prep threads list this as a clean warm-up problem frequently paired with Merge K Sorted Lists later 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]

Explanation: Elements from both lists are interleaved in sorted order.

Example 2

Input

list1 = [], list2 = []

Output

[]

Explanation: Both empty — result is empty.

Example 3

Input

list1 = [], list2 = [0]

Output

[0]

Explanation: One list empty — result is just the other list.

Approaches

1. Iterative with dummy head

Create a dummy head so you always have a node to append to. Walk both lists, picking the smaller node each step. Attach any remaining nodes 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 the remaining non-empty list
  tail.next = list1 !== null ? list1 : list2;
  return dummy.next;
}

Tradeoff: O(m+n) time, O(1) space. The dummy head removes all empty-list special cases. This is the canonical answer Gusto expects.

2. Recursive

Pick the smaller head node and recurse on the remainder.

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 uses O(m+n) stack space. Offer it as an alternative but prefer the iterative version for large lists.

Gusto-specific tips

Gusto interviewers watch for the dummy head pattern — it shows you've solved linked-list problems before and know how to avoid special-casing the head insertion. Trace through the empty-list cases verbally before writing code. Note that 'tail.next = list1 ?? list2' is fine because once the while loop exits, at most one list is non-null.

Common mistakes

Forgetting to attach the remaining tail — after one list is exhausted the other may still have nodes.
Not using a dummy head — leads to verbose if/else for the very first node insertion.
Advancing both list pointers regardless of which was chosen — only advance the pointer for the node you just appended.
In the recursive version, not handling both null base cases before comparing values.

Follow-up questions

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

Merge K sorted lists (LC 23) — use a min-heap or divide-and-conquer.
Sort a linked list (LC 148) — merge sort using this as the merge step.
How would you verify correctness of the merge without reconstructing an array?

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 instead of special-casing the first node?

A dummy head means tail.next always has somewhere to point. Without it you need separate logic to establish the result head, which is error-prone and harder to read.

Is it OK to reuse the original nodes rather than creating new ones?

Yes — the problem says to splice together the original nodes, which is more efficient than allocating new nodes.

What if one list is much longer than the other?

The algorithm handles this naturally — after the while loop exits you attach the remainder of the longer list in O(1) by pointing tail.next at the remaining head.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →