Skip to main content

3. Merge Two Sorted Lists

easyAsked at Mercury

Merge two sorted linked lists into one sorted list by splicing nodes.

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

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 list.

Constraints

  • 0 <= list length <= 50
  • -100 <= node value <= 100
  • Both lists sorted ascending

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. Brute force collect

Copy both lists into an array, sort, rebuild list.

Time
O((n+m) log(n+m))
Space
O(n+m)
const arr=[]; while(l1){arr.push(l1.val);l1=l1.next;}
while(l2){arr.push(l2.val);l2=l2.next;}
arr.sort((a,b)=>a-b);

Tradeoff:

2. Iterative two-pointer splice

Walk both heads with a dummy node, attach the smaller each step. Linear and in-place.

Time
O(n+m)
Space
O(1)
function mergeTwoLists(l1, l2) {
  const dummy = { 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:

Mercury-specific tips

At Mercury, this maps to merging settled-card and ACH event streams in posting-time order for the same business account, so emphasize stable ordering when timestamps tie.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →