Skip to main content

3. Merge Two Sorted Lists

easyAsked at Wise

Merge two sorted linked lists into one — Wise frames this around merging two sorted FX rate feeds into a single time-ordered stream.

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 its head.

Constraints

  • 0 <= length <= 50
  • Values are sorted non-decreasing
  • -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. Brute force

Dump 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); // rebuild

Tradeoff:

2. Two pointers with dummy head

Walk both lists in parallel, append the smaller node.

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

Tradeoff:

Wise-specific tips

At Wise this is the gateway to a follow-up about merging k sorted rate feeds — sketch the heap version even if not asked.

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

Practice these live with InterviewChamp.AI →