Skip to main content

3. Merge Two Sorted Lists

easyAsked at PayPal

Merge two sorted linked lists into one sorted list by splicing nodes together. PayPal asks this as a warm-up to gauge pointer comfort — the same primitive they use when merging two sorted streams of authorized and captured payments by timestamp.

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

Source citations

Public interview reports confirming this problem appears in PayPal loops.

  • Glassdoor (2025-12)— PayPal SDE-2 phone screen, reported across multiple US locations.
  • LeetCode Discuss (2026-Q1)— Common follow-up to Two Sum at PayPal.

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. Build new list with copies

Allocate new nodes and copy values from the source lists. Compare current values, copy smaller.

Time
O(n+m)
Space
O(n+m)
function mergeTwoLists(l1, l2) {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (l1 && l2) {
    const node = new ListNode(l1.val <= l2.val ? (l1 = l1.next, l1.val) : l2.val);
    tail.next = node;
    tail = node;
  }
  return dummy.next;
}

Tradeoff: Allocates O(n+m) new nodes. Doesn't reuse existing memory.

2. In-place splice with dummy head (optimal)

Use a dummy head and a tail pointer. Compare heads; splice the smaller one onto tail and advance.

Time
O(n+m)
Space
O(1)
function mergeTwoLists(l1, l2) {
  const dummy = new ListNode(0);
  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: O(1) extra space. The dummy-head trick eliminates head-pointer edge cases — same pattern PayPal uses for transaction-event stream merging.

PayPal-specific tips

PayPal expects the dummy-head pattern to feel reflexive. Bonus signal: explain that for stable ordering (when timestamps tie), the choice of <= vs < determines which stream wins — relevant when reconciling two payment-event streams where ordering must be deterministic.

Common mistakes

  • Forgetting to append the remaining list (`tail.next = l1 || l2`) — drops the tail.
  • Using `<` instead of `<=` — works for this problem but produces non-stable ordering, which matters when extending to k-way merge.
  • Allocating new nodes instead of splicing — wastes memory at scale.

Follow-up questions

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

  • Merge k sorted lists (LC 23).
  • Merge two sorted lists in reverse order.
  • What if the lists are doubly-linked?

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

Without one, you'd need a branch to set the initial head pointer. The dummy lets you treat the first node like any other, then return dummy.next at the end.

Is recursion better?

It's cleaner to read but uses O(n+m) stack space. At PayPal scale (long streams), iteration with O(1) space is preferred.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →