Skip to main content

3. Merge Two Sorted Lists

easyAsked at Square

Splice two sorted linked lists into one sorted list. Square uses this to test pointer-discipline — the same care needed when reconciling two ordered streams of transaction events for offline-first sync.

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

Source citations

Public interview reports confirming this problem appears in Square loops.

  • LeetCode Discuss (2025)— Square Reader firmware team phone screen.
  • Glassdoor (2026-Q1)— Cash App backend onsite.

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

  • Number of nodes in both lists is in [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. Convert to array, sort, rebuild

Collect all values into an array, sort it, build a new linked list.

Time
O((n+m) log(n+m))
Space
O(n+m)
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 cur = dummy;
  for (const v of vals) { cur.next = { val: v, next: null }; cur = cur.next; }
  return dummy.next;
}

Tradeoff: Ignores that inputs are sorted; Square interviewers will flag the wasted log factor.

2. Two-pointer splice with dummy head

Use a dummy head. Compare list1.val vs list2.val, splice the smaller onto tail, advance. Attach the leftover when one side is exhausted.

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: Single pass, O(1) extra space (we reuse the input nodes). The dummy head dodges special-casing the first node.

Square-specific tips

Square interviewers grade the dummy-head pattern as a signal that you've internalized linked-list discipline. They also like when you mention reusing the original nodes (no allocation), which echoes their focus on memory-tight POS firmware. Always say '<=' instead of '<' for stable ordering — they ask about stability.

Common mistakes

  • Forgetting to attach the remaining list when one side is exhausted.
  • Using a strict '<' comparison, which breaks stability when equal values appear.
  • Allocating new nodes — wastes memory; reuse the existing ones.

Follow-up questions

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

  • Merge K sorted lists (LC 23) — heap or divide & conquer.
  • Merge two sorted lists in-place but reversed at the same time.
  • How does this generalize to merging N event streams for offline POS sync?

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 'is this the first node?' branch from your splice loop. Cleaner code, fewer bugs.

Is the merge stable?

Yes if you use '<=' (take from list1 on tie). With '<' you'd take from list2 on tie, which is also stable but less conventional.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →