Skip to main content

21. Merge Two Sorted Lists

easyAsked at Apple

Merge Two Sorted Lists is Apple's canonical linked-list warm-up. The dummy-node trick — start with a dummy then thread the smaller of the two heads onto its tail — keeps the code clean and edge-case-free. Apple grades on whether you reach for the dummy unprompted.

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

Source citations

Public interview reports confirming this problem appears in Apple loops.

  • Glassdoor (2026-Q1)— Apple SWE phone-screen reports list Merge Two Sorted Lists as a recurring 15-minute linked-list warm-up.
  • Blind (2025-11)— Apple new-grad reports cite Merge Two Sorted Lists as the canonical linked-list easy.

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. Iterative with dummy node (optimal)

Allocate a dummy head. Walk both lists, splicing the smaller node onto the dummy's tail. Append the remainder of whichever list is non-empty at the end.

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

Tradeoff: Linear time, in-place (splices existing nodes — no allocation). The dummy avoids the 'first node is special' branch. Apple's preferred answer.

2. Recursive

If either list is null, return the other. Otherwise pick the smaller head, recurse on its rest + the other list, splice into the picked head's next.

Time
O(n + m)
Space
O(n + m) recursion stack
function mergeTwoLists(list1, list2) {
  if (!list1) return list2;
  if (!list2) 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: Cleaner three-line recursion but pays O(n+m) stack space. Apple will accept either; the iterative version is preferred at senior levels because of the space.

Apple-specific tips

Apple cares about the dummy node specifically. Saying 'I'll use a dummy head to avoid the empty-result edge case' is worth the next ten minutes of the interview. Without the dummy, you spend code on 'is this the first node?' branching that produces bugs. The dummy is the standard linked-list interview pattern for any 'build a new list' problem.

Common mistakes

  • Forgetting to advance tail = tail.next inside the loop.
  • Forgetting the trailing tail.next = list1 || list2 — leaves the result truncated.
  • Allocating new nodes instead of splicing existing ones — works correctness-wise but doubles memory.

Follow-up questions

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

  • Merge k Sorted Lists (LC 23) — heap of heads, or pairwise merge.
  • Sort List (LC 148) — merge sort on linked list, uses this as the merge step.
  • Merge Two Sorted Arrays in-place — different data structure, same idea.

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?

Because the result's head isn't known until after the first comparison. The dummy gives us a tail to write to without a special case for 'first node ever.'

Iterative or recursive?

Iterative for senior interviews (O(1) space). Recursive is shorter to write and fine for an easy.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →