Skip to main content

3. Merge Two Sorted Lists

easyAsked at Baidu

Combine two sorted linked lists into one sorted list.

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

Problem

You are given the heads of two sorted linked lists list1 and list2. Splice the nodes together in sorted order and return the head of the merged list.

Constraints

  • 0 <= total nodes <= 100
  • -100 <= Node.val <= 100
  • Both input lists are sorted non-decreasing

Examples

Example 1

Input
list1 = [1,2,4], list2 = [1,3,4]
Output
[1,1,2,3,4,4]

Example 2

Input
list1 = [], list2 = []
Output
[]

Approaches

1. Brute force

Collect all node values, sort, rebuild a list.

Time
O(n log n)
Space
O(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);// rebuild list

Tradeoff:

2. Two-pointer merge

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

Baidu-specific tips

Baidu often follows this with a 'k-way merge' twist mirroring how their crawler merges sorted URL queues across many fetchers.

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

Practice these live with InterviewChamp.AI →