Skip to main content

3. Merge Two Sorted Lists

easyAsked at Coupang

Merge two sorted linked lists into one sorted list — Coupang uses it to test pointer hygiene before merging delivery-route streams.

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. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

Constraints

  • 0 <= count <= 50 per list
  • -100 <= Node.val <= 100
  • Both lists 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. Brute force

Collect all values, sort, rebuild list.

Time
O((n+m) log(n+m))
Space
O(n+m)
const arr = [];
let a=list1,b=list2;
while(a){arr.push(a.val);a=a.next;}
while(b){arr.push(b.val);b=b.next;}
arr.sort((x,y)=>x-y);
// rebuild

Tradeoff:

2. Two-pointer merge

Walk both pointers; splice smaller into tail.

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:

Coupang-specific tips

Coupang interviewers like a dummy-node pattern and ask follow-ups about merging k delivery-event streams.

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 Coupang interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →