Skip to main content

3. Merge Two Sorted Lists

easyAsked at N26

Merge two sorted linked lists into one sorted list. N26 uses this to probe pointer hygiene before scaling up to merging chronologically sorted multi-currency transaction streams.

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

Problem

Merge two sorted linked lists into one sorted list. The result should be spliced together from the nodes of the first two lists. Return the head of the merged list.

Constraints

  • 0 <= list length <= 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 resort

Flatten values into array, sort, rebuild list.

Time
O((n+m) log(n+m))
Space
O(n+m)
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-pointer splice

Walk both lists with a dummy head; attach the smaller node at 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:

N26-specific tips

N26 graders reward you for naming the analogy to merging EUR and GBP transaction feeds during nightly settlement.

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

Practice these live with InterviewChamp.AI →