Skip to main content

3. Merge Two Sorted Lists

easyAsked at Ola

Merge two ascending 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. Splice them together into one sorted list by reusing the nodes of the two given lists and return the head.

Constraints

  • 0 <= list size <= 50
  • -100 <= Node.val <= 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. Brute force

Copy both lists into an array, sort, and rebuild a linked list.

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

Tradeoff:

2. Two-pointer splice

Walk both heads with a dummy node, picking the smaller each step. O(n+m) and no extra allocation beyond the dummy.

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:

Ola-specific tips

Ola uses this to gauge pointer hygiene; relate it to merging incoming GPS pings from two driver streams without buffering them in memory.

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

Practice these live with InterviewChamp.AI →