Skip to main content

21. Merge Two Sorted Lists

easyAsked at Twilio

Merge Two Sorted Lists is Twilio's linked-list mechanics check: splice two sorted lists into a single sorted list in O(m + n). The dummy-head pattern is mandatory; candidates who special-case the first node are flagged for handling unnecessary edge cases.

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

Source citations

Public interview reports confirming this problem appears in Twilio loops.

  • Glassdoor (2026-Q1)— Reported in Twilio backend SWE on-site reports as a warm-up before LRU Cache.
  • LeetCode Discuss (2025-11)— Listed across Twilio interview reports as a phone-screen second-round question.

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. Collect into an array, sort, rebuild (rejected)

Walk both lists into an array, sort, then build a new linked list.

Time
O((m + n) log (m + n))
Space
O(m + n)
function mergeViaSort(l1, l2) {
  const vals = [];
  while (l1) { vals.push(l1.val); l1 = l1.next; }
  while (l2) { vals.push(l2.val); l2 = l2.next; }
  vals.sort((a, b) => a - b);
  const dummy = { val: 0, next: null };
  let tail = dummy;
  for (const v of vals) { tail.next = { val: v, next: null }; tail = tail.next; }
  return dummy.next;
}

Tradeoff: Ignores the input being already sorted, which is the whole point of the problem. Twilio will reject this; the optimal merge uses the existing sort order in O(m + n).

2. Two-pointer splice with dummy head (optimal)

Walk both lists in lockstep, append the smaller head to the tail, advance that list. Attach the remainder of the non-empty list at the end.

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

Tradeoff: Splices in place — O(1) extra space because we reuse the existing nodes. `tail.next = l1 || l2` is the elegant attach-remainder idiom: at least one is null, so it works without an explicit branch.

Twilio-specific tips

Twilio interviewers grade this on three things: dummy head, in-place splicing (no new node allocation), and the `tail.next = l1 || l2` remainder attach. The most common rejection signal is candidates who allocate new nodes — Twilio's reviewers consider that a missed-the-point answer. Mentioning that this is the inductive step in merge sort (and thus the base case for LC 23 Merge K Sorted Lists) is a strong signal.

Common mistakes

  • Allocating new nodes instead of splicing existing ones — wastes O(m + n) space the problem doesn't require.
  • Forgetting the remainder attach when one list is exhausted — leaves the merged list truncated.
  • Using `<` instead of `<=` for the comparison, which technically still works but doesn't preserve stability if the question is extended.

Follow-up questions

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

  • What if you had K sorted lists instead of 2? (LC 23 — min-heap of size K, or pairwise merge-sort style.)
  • What if the lists were doubly-linked? (Same algorithm — you'd also fix the prev pointers in the splice step.)
  • How would you write this recursively? (Compare heads, recurse on the smaller's next, return the chosen head with its merged tail.)

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 is the dummy head the standard pattern?

It eliminates the 'is this the first node?' branch. Without a dummy, you'd have to special-case the first append, which is a common off-by-one bug under interview pressure.

Why `tail.next = l1 || l2` instead of two while-loops to drain each list?

Because the remaining list is already sorted and already linked — there is nothing to do but attach it. Walking it node-by-node would be correct but wasteful and signals that the candidate didn't see the elegance.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →