Skip to main content

3. Merge Two Sorted Lists

easyAsked at Chime

Merge two sorted linked lists into one sorted list by splicing nodes together.

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 linked list.

Constraints

  • 0 <= number of nodes <= 50
  • -100 <= Node.val <= 100
  • Both inputs are sorted in non-decreasing order.

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 into array

Copy both lists into array, sort, rebuild a list.

Time
O((n+m) log(n+m))
Space
O(n+m)
const arr = [];
while (list1) { arr.push(list1.val); list1 = list1.next; }
while (list2) { arr.push(list2.val); list2 = list2.next; }
arr.sort((a,b)=>a-b);
// rebuild list from arr

Tradeoff:

2. Two-pointer splice

Walk both lists with a dummy head, splicing the smaller node each step.

Time
O(n+m)
Space
O(1)
function mergeTwoLists(l1, l2) {
  const dummy = { val: 0, 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:

Chime-specific tips

Chime expects clean pointer manipulation; this models merging two sorted streams like ACH credit and debit batches into a single posting queue.

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

Practice these live with InterviewChamp.AI →