Skip to main content

3. Merge Two Sorted Lists

easyAsked at Tesla

Merge two sorted linked lists into one sorted list.

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

Problem

You are given two sorted linked lists l1 and l2. Splice them into one sorted list and return the head. The result must reuse the original nodes.

Constraints

  • 0 <= total nodes <= 100
  • -100 <= node.val <= 100
  • Inputs are sorted ascending

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 re-sort

Dump values into an array, sort, rebuild list.

Time
O(n log n)
Space
O(n)
const vals = [];
for (let p of [l1,l2]) while (p) { vals.push(p.val); p = p.next; }
vals.sort((a,b)=>a-b);
// rebuild...

Tradeoff:

2. Dummy head merge

Walk both lists with a tail pointer attached to a dummy. Splice the smaller head 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:

Tesla-specific tips

Tesla likes pointer-clean merges — they're the linked-list analog of fusing two sensor streams into one timestamp-sorted feed and the in-place version avoids heap allocations in the hot path.

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

Practice these live with InterviewChamp.AI →