Skip to main content

3. Merge Two Sorted Lists

easyAsked at Quora

Merge two sorted linked lists into one sorted list.

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

Constraints

  • 0 <= total nodes <= 50
  • -100 <= Node.val <= 100
  • Both lists sorted non-decreasing

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 all values into an array and sort.

Time
O(n log n)
Space
O(n)
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);
// rebuild list

Tradeoff:

2. Two-pointer splice

Walk both heads with a dummy node and pick the smaller value 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:

Quora-specific tips

Quora reaches for merge-sorted patterns because their answer-feed merges ranked streams from followed topics, followed users, and recency in real time.

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

Practice these live with InterviewChamp.AI →