Skip to main content

3. Merge Two Sorted Lists

easyAsked at DigitalOcean

Merge two ascending linked lists into one sorted list — DigitalOcean uses this to test pointer hygiene that resembles merging billing entries from two ledger streams.

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

Problem

Merge two sorted linked lists by splicing their nodes together to form a single sorted list. Return the head of the merged list.

Constraints

  • 0 <= length of each list <= 50
  • -100 <= node.val <= 100
  • Both lists 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 sort

Walk both lists, push values to array, sort, rebuild list.

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

Tradeoff:

2. Two-pointer splice

Use a dummy head; advance the pointer with smaller current value. Avoids extra allocation.

Time
O(n+m)
Space
O(1)
function merge(l1, l2) {
  const dummy = { val: 0, 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:

DigitalOcean-specific tips

DigitalOcean prefers the in-place splice because their internal services rebuild billing-line streams without re-allocating large arrays under sustained tenant load.

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

Practice these live with InterviewChamp.AI →