Skip to main content

3. Merge Two Sorted Lists

easyAsked at Coursera

Merge two sorted linked lists into one — Coursera uses this to test pointer hygiene in a sorted-content-streams setting.

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

Problem

You are given the heads of two sorted linked lists list1 and list2. Splice them together into one sorted list and return the head of the merged list.

Constraints

  • 0 <= n1 + n2 <= 5000
  • -100 <= Node.val <= 100
  • Both inputs 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 everything 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. Two-pointer splice

Dummy node + tail; attach smaller head at each step.

Time
O(n+m)
Space
O(1)
function merge(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:

Coursera-specific tips

Coursera interviewers frame this as merging two sorted recommendation streams (e.g. relevance-ranked vs. recency-ranked course feeds) — call that out and show you can keep it O(1) extra space.

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

Practice these live with InterviewChamp.AI →