Skip to main content

4. Merge Two Sorted Lists

easyAsked at Notion

Merge two sorted singly-linked lists into one. Notion uses this to check whether you can write clean pointer code — relevant to merging two CRDT operation logs.

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

Source citations

Public interview reports confirming this problem appears in Notion loops.

  • Glassdoor (2026-Q1)— Notion uses this as a 15-min linked-list warm-up.
  • LeetCode Discuss (2025-12)— Often paired with a follow-up about merging K sorted CRDT logs.

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 to array, sort, rebuild

Walk both lists, push values to an array, sort, rebuild.

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

Tradeoff: Throws away sortedness. Wastes the linear-time merge structure.

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

Use a dummy head + tail pointer. Compare heads of both lists and splice the smaller in. Attach the remainder at the end.

Time
O(m+n)
Space
O(1)
function mergeTwoLists(a, b) {
  const dummy = { 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: Linear time, O(1) extra space because we splice existing nodes. The dummy head avoids the 'is this the first node?' branch.

Notion-specific tips

Notion grades pointer hygiene here: candidates who write dummy-head merges cleanly score higher than those who special-case the first node. Bonus signal: mention that this generalizes to merge-K (LC 23) which is closer to merging multiple CRDT operation streams.

Common mistakes

  • Forgetting `tail.next = a || b` — drops the remainder.
  • Allocating new nodes instead of splicing existing ones — wastes O(n) memory.
  • Off-by-one with the dummy head — returning dummy instead of dummy.next.

Follow-up questions

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

  • Merge K sorted lists (LC 23).
  • Merge in-place arrays (LC 88).
  • What if lists are stored as a stream — no length known?

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 use a dummy head?

It removes the 'first iteration is special' branch. Without it you'd need to handle 'is this the head?' on every iteration.

Can I do this recursively?

Yes, in O(m+n) time and O(m+n) recursion-stack space. For huge lists, prefer iterative.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →