Skip to main content

3. Merge Two Sorted Lists

easyAsked at Adobe

Merge two sorted singly-linked lists into one sorted list, reusing the existing nodes. Adobe uses this as the pointer-manipulation litmus test — the same merge logic underlies layer compositing where two ordered Z-stacks combine into one.

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

Source citations

Public interview reports confirming this problem appears in Adobe loops.

  • Glassdoor (2026-Q1)— Adobe SDE phone screens commonly use this.
  • Blind (2025-12)— Adobe MTS reported this as a 30-min phone screen problem.

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. Recursive

Compare heads, recurse on the smaller's next.

Time
O(n + m)
Space
O(n + m) call stack
function mergeTwoLists(l1, l2) {
  if (!l1) return l2;
  if (!l2) return l1;
  if (l1.val <= l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
}

Tradeoff: Elegant but stack grows linearly. Adobe will ask about iterative for production-scale lists.

2. Iterative with dummy head

Use a sentinel dummy node; tail-append the smaller current; advance.

Time
O(n + m)
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: O(1) extra space. The dummy-head trick avoids special-casing the very first append. Adobe interviewers reward this technique because it generalizes to k-way merge in compositing pipelines.

Adobe-specific tips

Adobe loves when you draw a layer-compositing analogy: two sorted lists of layer Z-indices merging into one. Mention that the dummy-head pattern is the same one you'd use when merging undo-stacks from two collaborative editing sessions in a creative tool.

Common mistakes

  • Forgetting to attach the leftover list after the loop — drops the tail.
  • Allocating new nodes instead of splicing — the problem says splice.
  • Off-by-one when advancing tail — losing the connection.

Follow-up questions

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

  • Merge k sorted lists (LC 23) — extends to a heap.
  • Merge sorted arrays in-place (LC 88) — array variant.
  • Merge sorted intervals — range version.

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

It removes a special case: without it, you'd need an 'if first iteration, head = ...' branch. The dummy lets you treat every append identically, then return dummy.next.

What if one list is much longer than the other?

The 'tail.next = l1 || l2' line at the end handles it in O(1) — you splice the remaining tail wholesale, no further comparisons.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →