Skip to main content

3. Merge Two Sorted Lists

easyAsked at Plaid

Merge two sorted linked lists into one sorted list. Plaid asks this because merging two pre-sorted streams of transactions from different bank feeds is a daily operation on their ETL pipeline.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Blind (2025)— Plaid data-engineering screen — framed as merging two transaction feeds.
  • LeetCode Discuss (2026-Q1)— Commonly reported Plaid intro.

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
[]

Approaches

1. Collect all values into an array and sort

Dump everything into an array, sort it, then rebuild a linked list.

Time
O((n+m) log(n+m))
Space
O(n+m)
function mergeTwoLists(a, b) {
  const vals = [];
  for (let n = a; n; n = n.next) vals.push(n.val);
  for (let n = b; n; n = n.next) vals.push(n.val);
  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: Throws away the sortedness you were given. Plaid would dock you for ignoring the precondition.

2. Two-pointer splice with dummy head

Walk both lists with two pointers and splice the smaller node each iteration. Dummy head sidesteps the 'which list is empty' branch.

Time
O(n+m)
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: In-place splicing — no allocation for new nodes. The dummy head removes a fistful of edge cases.

Plaid-specific tips

Plaid grades this on whether you reuse existing nodes versus allocating new ones. In their data pipeline, redundant allocation per transaction blows the memory budget. State out loud that you're splicing, not copying. Bonus signal: mention how this generalizes to merging k sorted feeds with a heap.

Common mistakes

  • Forgetting to attach the remainder of the non-empty list with tail.next = a || b.
  • Using strict less-than instead of <= — breaks stability when ties matter for downstream ordering.
  • Mutating list1 and list2 in ways that surprise the caller — be explicit about ownership.

Follow-up questions

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

  • Merge k sorted lists (LC 23) with a min-heap.
  • Merge in-place when both lists may have duplicates that need de-duping.
  • What if one stream is unbounded — how do you back-pressure?

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 special case for the first node. Without it you need an if-statement to set the head, then another to advance the tail.

Is this stable?

Yes, because we use <= rather than <. Stability matters when the values are transaction amounts and a tiebreaker like timestamp lives in the original order.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →