Skip to main content

3. Merge Two Sorted Lists

easyAsked at Lyft

Combine two sorted singly-linked lists into one sorted list.

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

Problem

Given the heads of two sorted linked lists list1 and list2, splice them into one sorted list and return its head. The result must be made by splicing the existing nodes (or you may build a new chain).

Constraints

  • 0 <= nodes in each list <= 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 = [0]
Output
[0]

Approaches

1. Collect-and-sort

Push all values into an array, sort, and rebuild.

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

Tradeoff:

2. Two pointer merge

Walk both lists with a dummy head; pick the smaller node each step. Single pass, in-place splicing.

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:

Lyft-specific tips

Lyft uses the dummy-head pattern when merging sorted streams of ride events; reach for it instead of special-casing the empty list.

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

Practice these live with InterviewChamp.AI →