Skip to main content

3. Merge Two Sorted Lists

easyAsked at Activision

Merge two sorted linked lists into one — Activision uses it to gauge pointer manipulation relevant to merging player feeds or sorted match logs.

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

Problem

Merge two sorted linked lists and return the head of the merged sorted list. The new list should be built by splicing nodes of the original two.

Constraints

  • 0 <= n <= 50 per list
  • -100 <= Node.val <= 100
  • Both lists are 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=[]
Output
[]

Approaches

1. Collect and sort

Extract all values, sort, rebuild list.

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

Tradeoff:

2. Two-pointer splice with dummy head

Walk both lists, attach the smaller node, advance. Dummy head simplifies edge cases.

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

Activision-specific tips

Activision values clean dummy-head usage here — it signals you write defensive code, important when merging telemetry streams from multiple game servers.

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

Practice these live with InterviewChamp.AI →