Skip to main content

3. Merge Two Sorted Lists

easyAsked at Instacart

Merge two sorted linked lists into one — Instacart maps this onto merging two ETA-sorted delivery queues into a single shopper feed.

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. Return the head of the merged list.

Constraints

  • 0 <= length of each list <= 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 and sort

Push all values into an array, sort, rebuild a list.

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

Tradeoff:

2. Two pointers with dummy head

Use a dummy node and append the smaller head at each step.

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:

Instacart-specific tips

Instacart's interviewers reward the dummy-head pattern — they'll ask how it generalizes to merging K courier feeds for batched dispatch.

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

Practice these live with InterviewChamp.AI →