Skip to main content

21. Merge Two Sorted Lists

easyAsked at Linear

Merge two sorted linked lists into one sorted list. Linear asks this as a foundational pointer problem — it directly primes the harder follow-up (Merge K Sorted Lists) and reveals whether you use a dummy head to simplify edge cases.

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

Source citations

Public interview reports confirming this problem appears in Linear loops.

  • Glassdoor (2025-12)— Reported as a linked-list warm-up in Linear SWE phone screen threads.
  • r/cscareerquestions (2025-10)— Mentioned as a first-round problem in recent Linear interview discussions.

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; the smaller becomes the result node, its next is the recursive merge of the rest.

Time
O(m + n)
Space
O(m + n)
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: Elegant and short, but O(m+n) call stack. On large lists this risks a stack overflow. Good for demonstrating recursion thinking.

2. Iterative with dummy head (optimal)

Use a dummy head to avoid edge cases. Walk both lists, picking the smaller node each time.

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

Tradeoff: O(m+n) time, O(1) space. The dummy head eliminates all special-casing for the initial head node — a standard linked-list trick worth mentioning by name.

Linear-specific tips

Mention the dummy-head technique explicitly: 'I'll use a sentinel node to avoid special-casing the result head.' Linear interviewers note whether you know this pattern — it signals familiarity with production linked-list code. Also name-drop the merge step from merge sort, since that's the connection they'll ask about.

Common mistakes

  • Not attaching the remaining tail — when one list is exhausted, curr.next should point to the remaining list (not loop through it).
  • Forgetting to return dummy.next instead of dummy — dummy itself is a sentinel, not a real result node.
  • Mutating the input nodes and not explaining the side effects — Linear interviewers may ask about in-place modification.

Follow-up questions

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

  • Merge K Sorted Lists (LC 23) — use a min-heap or divide-and-conquer.
  • Sort List (LC 148) — applies this merge step in a full merge sort on a linked list.
  • How would you merge two sorted arrays instead of linked lists?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

What is a dummy head and why use it?

A dummy (sentinel) node before the result list means you never have to special-case setting the head — every node is appended via curr.next = ... uniformly. Return dummy.next at the end.

Can I do this without extra nodes?

Yes — pick whichever head is smaller as the result head, then iteratively relink. But this requires edge-case handling that the dummy node eliminates cleanly.

Why is the recursive solution O(m+n) space?

Each recursive call adds a frame to the call stack before returning. With m+n calls total, the stack depth is O(m+n).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →