Skip to main content

3. Merge Two Sorted Lists

easyAsked at Glassdoor

Merge two sorted linked lists into one sorted list — Glassdoor uses this to test pointer hygiene under interleaved inputs.

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. The list should be made by splicing together the nodes of the first two lists.

Constraints

  • 0 <= each list length <= 50
  • -100 <= node.val <= 100
  • Both lists are sorted ascending

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

Dump both lists into an array and sort.

Time
O((m+n) log(m+n))
Space
O(m+n)
const arr = [];
for (let n=l1; n; n=n.next) arr.push(n.val);
for (let n=l2; n; n=n.next) arr.push(n.val);
arr.sort((a,b)=>a-b);
// rebuild list from arr

Tradeoff:

2. Two-pointer splice

Walk both lists with a dummy head and splice the smaller node.

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

Glassdoor-specific tips

Glassdoor likes the dummy-head pattern called out explicitly — their review-merge pipelines use the same sentinel trick to avoid null edge-cases.

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

Practice these live with InterviewChamp.AI →