Skip to main content

3. Merge Two Sorted Lists

easyAsked at Yelp

Merge two sorted linked lists into one sorted list — Yelp uses this as the conceptual cousin to merging two relevance-sorted review feeds before final ranking.

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

Problem

You are given the heads of two sorted linked lists. Merge them into one sorted list by splicing nodes from the inputs. Return the head of the merged list.

Constraints

  • 0 <= length of each list <= 50
  • -100 <= Node.val <= 100
  • Both lists are sorted non-decreasingly

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

Dump both lists into an array, sort, rebuild.

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

Tradeoff:

2. Dummy head + two pointers

Walk both lists, splicing the smaller node onto a dummy 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:

Yelp-specific tips

Yelp interviewers reward the dummy-head trick and will probe whether you can extend it to k-way merging of relevance-sorted review streams for the search results page.

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

Practice these live with InterviewChamp.AI →