Skip to main content

3. Merge Two Sorted Lists

easyAsked at Asana

Merge two sorted linked lists into one sorted list by splicing nodes together. Asana asks this to confirm you can handle pointer manipulation cleanly — a building block for their dependency-resolution merge step.

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

Source citations

Public interview reports confirming this problem appears in Asana loops.

  • Glassdoor (2026-Q1)— Asana backend phone screen warmup.
  • LeetCode Discuss (2025-11)— Common pointer warmup before graph traversal questions.

Problem

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list 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. Build a new list from scratch

Walk both, allocate new nodes with each comparison.

Time
O(n+m)
Space
O(n+m)
function mergeTwoLists(a, b) {
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (a && b) {
    tail.next = { val: a.val <= b.val ? a.val : b.val, next: null };
    if (a.val <= b.val) a = a.next; else b = b.next;
    tail = tail.next;
  }
  // append remainder by cloning — wasteful
  return dummy.next;
}

Tradeoff: Works but allocates O(n+m) new nodes. Asana wants the in-place splice.

2. Iterative splice with dummy head

Use a dummy node and a tail pointer; repeatedly attach the smaller head and advance.

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

Tradeoff: O(1) extra space by re-using the input nodes. The dummy-head trick removes the special case for the first append.

Asana-specific tips

Asana grades on whether you spot the dummy-head pattern — without it, you write 6 lines of special-case logic for the first node. Mentioning that this is a building block for k-way merges (which they use internally for activity feed aggregation) earns culture points.

Common mistakes

  • Forgetting to attach the leftover tail when one list is exhausted.
  • Allocating new nodes instead of re-splicing — wastes memory.
  • Off-by-one when advancing the tail pointer.

Follow-up questions

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

  • Merge k sorted lists (LC 23).
  • Do it recursively — what's the stack depth?
  • What if the lists could have cycles?

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 a dummy node?

The dummy unifies the empty-result and non-empty-result cases. Without it, you'd need separate logic to set head on the first iteration, then attach to head.next afterward.

Does the recursive version have hidden costs?

Yes — it uses O(n+m) call-stack space, which can stack-overflow on long lists. Iterative is safer in production.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →