Skip to main content

3. Merge Two Sorted Lists

easyAsked at Nubank

Merge two sorted ledger entry streams into a single chronological feed.

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

Problem

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list and return the head of the merged list.

Constraints

  • 0 <= nodes <= 50
  • -100 <= Node.val <= 100

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. Collect and sort

Put all values in an array and sort.

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

Tradeoff:

2. Two pointers

Use a dummy node; pick the smaller head each step.

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

Nubank-specific tips

Nubank looks for the merge pattern as a building block for reconciling event streams from card-network and core-ledger systems.

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

Practice these live with InterviewChamp.AI →