Skip to main content

3. Merge Two Sorted Lists

easyAsked at Unity

Merge two sorted linked lists into one sorted list. Unity uses this to probe pointer hygiene used in entity update queues.

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

Problem

You are given the heads of two sorted linked lists list1 and list2. Merge them into one sorted list spliced together from the nodes of the first two. Return the head of the merged list.

Constraints

  • 0 <= length of each list <= 50
  • Both lists are sorted in non-decreasing order

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

Push all values into an array, sort, rebuild list.

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

Tradeoff:

2. Two-pointer splice

Walk both lists with a tail pointer, splicing smaller node each step. Attach the remainder at the end.

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:

Unity-specific tips

Unity prefers in-place splicing because allocations in a frame-budget runtime would trigger GC spikes mid-gameplay.

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

Practice these live with InterviewChamp.AI →