Skip to main content

3. Merge Two Sorted Lists

easyAsked at Roblox

Merge two sorted linked lists into a single sorted linked 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 existing nodes and return the head of the merged list.

Constraints

  • 0 <= length <= 50
  • -100 <= node value <= 100
  • Both lists are 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. Copy into array and sort

Flatten then sort then rebuild a list.

Time
O((n+m) log(n+m))
Space
O(n+m)
const arr = [];
for (let n=list1; n; n=n.next) arr.push(n.val);
for (let n=list2; n; n=n.next) arr.push(n.val);
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(a, b) {
  const dummy = { next: null };
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a || b;
  return dummy.next;
}

Tradeoff:

Roblox-specific tips

Roblox engineers like seeing in-place pointer splicing because the same pattern shows up when merging two ordered event streams from the physics tick on a busy server.

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

Practice these live with InterviewChamp.AI →