Skip to main content

3. Merge Two Sorted Lists

easyAsked at Grab

Merge two sorted linked lists into one — a Grab favorite for testing pointer hygiene.

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

Problem

Given the heads of two sorted linked lists, splice them together by reusing nodes from the two input lists and return the head of the new merged sorted list.

Constraints

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

Examples

Example 1

Input
l1 = [1,2,4], l2 = [1,3,4]
Output
[1,1,2,3,4,4]

Example 2

Input
l1 = [], l2 = [0]
Output
[0]

Approaches

1. Collect and sort

Extract values into an array, sort, rebuild.

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

Tradeoff:

2. Two-pointer splice

Walk both lists with a dummy head, attaching the smaller node each step.

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:

Grab-specific tips

Grab phones often follow up with 'merge K sorted streams' to map to their order-pipeline architecture — say it explicitly to score signal.

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

Practice these live with InterviewChamp.AI →