Skip to main content

3. Merge Two Sorted Lists

easyAsked at Revolut

Merge two ascending linked lists into one, a Revolut warm-up that mirrors merging two time-ordered FX trade streams into a single tape.

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

Problem

Given the heads of two sorted linked lists, merge them into one sorted list by splicing the nodes. Return the head of the merged list.

Constraints

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

Dump both lists to an array, sort, rebuild.

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

Tradeoff:

2. Two pointers, splice

Walk both lists, attach smaller node. Returns in O(m+n) with O(1) extra.

Time
O(m+n)
Space
O(1)
function merge(a,b){
  const dummy={next:null}; let t=dummy;
  while(a && b){
    if(a.val<=b.val){t.next=a;a=a.next}else{t.next=b;b=b.next}
    t=t.next;
  }
  t.next = a||b;
  return dummy.next;
}

Tradeoff:

Revolut-specific tips

Revolut likes the streaming-merge framing — interviewers nod when you mention this is how their trade-tape collator interleaves EUR and GBP feeds in monotonic timestamp order.

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

Practice these live with InterviewChamp.AI →