21. Merge Two Sorted Lists

Q: Why use a dummy node?

Without it, you'd need a conditional to initialize the head of the result list — either list1 or list2 depending on the first comparison. The dummy makes every step uniform: always append to tail.next.

Q: Is it safe to modify the original nodes?

The problem says 'splice together the nodes of the first two lists' — so yes, in-place pointer rewiring is expected. If immutability were required, you'd allocate new nodes.

Q: What happens if one list is much longer than the other?

The while loop runs m+n iterations at most, then the longer list's tail is attached in O(1). Total time is O(m+n) regardless of the length imbalance.

easyAsked at eBay

eBay's search-ranking pipeline merges sorted result streams from multiple indices — the classic k-way merge problem reduces to this two-list base case. Interviewers use it to test pointer discipline and the dummy-node trick that eliminates edge-case conditionals. Mastering this sets you up for Merge K Sorted Lists in later rounds.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in eBay loops.

Glassdoor (2025-12)— Cited in eBay onsite reports as a linked-list fundamentals problem in the first coding round.
Blind (2025-10)— eBay new-grad prep threads recommend Merge Two Sorted Lists as a must-know before attempting Merge K Sorted Lists in later rounds.

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]

Explanation: Compare heads, take the smaller, advance that pointer, repeat.

Example 2

Input

list1 = [], list2 = []

Output

[]

Explanation: Both empty — return null.

Example 3

Input

list1 = [], list2 = [0]

Output

[0]

Explanation: One list is empty — return the other.

Approaches

1. Iterative with dummy node

Use a dummy head node to simplify list construction. Advance the tail pointer by picking the smaller head from list1 or list2 at each step. Append the remaining non-null list at the end.

Time: O(m + n)
Space: O(1)

function mergeTwoLists(list1, list2) {
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (list1 !== null && list2 !== null) {
    if (list1.val <= list2.val) {
      tail.next = list1;
      list1 = list1.next;
    } else {
      tail.next = list2;
      list2 = list2.next;
    }
    tail = tail.next;
  }
  tail.next = list1 !== null ? list1 : list2; // attach remaining
  return dummy.next;
}

Tradeoff: O(1) space — the canonical answer. The dummy node removes the need to special-case an empty result list. This is the pattern eBay expects.

2. Recursive

Compare the two heads. Set the smaller head's next to the result of recursing on the rest, and return the smaller head.

Time: O(m + n)
Space: O(m + n) call stack

function mergeTwoLists(list1, list2) {
  if (list1 === null) return list2;
  if (list2 === null) 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 concise. O(m+n) call-stack depth — a concern for very long lists. Good to know but defer to iterative in production contexts.

eBay-specific tips

Always mention the dummy-node trick before coding: 'I'll use a dummy head to avoid special-casing an empty result list — the real head is dummy.next.' eBay engineers care about clean, production-quality code. The tail.next = list1 ?? list2 line at the end (or the conditional) shows you understand that at most one list is non-null when the while loop exits, making the append O(1).

Common mistakes

Forgetting to advance tail = tail.next after appending a node — creates an infinite loop.
Using tail.next = list1 || list2 in JavaScript — list1 = 0 would be falsy; use an explicit null check.
Not returning dummy.next — returning dummy gives the caller the dummy node's val (0) as if it were real data.
Recursing without base cases — both null checks are required before comparing values.

Follow-up questions

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

Merge K Sorted Lists (LC 23) — generalize using a min-heap; this problem is the base case.
Sort List (LC 148) — merge sort on a linked list; the merge step is exactly this problem.
How would you merge two sorted lists without modifying the original nodes (i.e., create new nodes)?

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 node?

Without it, you'd need a conditional to initialize the head of the result list — either list1 or list2 depending on the first comparison. The dummy makes every step uniform: always append to tail.next.

Is it safe to modify the original nodes?

The problem says 'splice together the nodes of the first two lists' — so yes, in-place pointer rewiring is expected. If immutability were required, you'd allocate new nodes.

What happens if one list is much longer than the other?

The while loop runs m+n iterations at most, then the longer list's tail is attached in O(1). Total time is O(m+n) regardless of the length imbalance.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →