Skip to main content

3. Merge Two Sorted Lists

easyAsked at Indeed

Merge two sorted linked lists into one sorted list — the linked-list merge that underpins Indeed's job-feed combination from multiple syndication sources.

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

Problem

Merge two sorted singly linked lists and return the head of a single sorted list spliced from the original nodes. Do not allocate new node objects beyond a dummy head.

Constraints

  • 0 <= total nodes <= 50
  • Values fit in 32-bit int
  • 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 sort

Push all values into an array and sort.

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);

Tradeoff:

2. Two-pointer splice

Walk both lists with a dummy tail, attaching the smaller head each step.

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

Indeed-specific tips

Indeed loves when you tie the dummy-head pattern to merging job-listing feeds — explain how this generalizes to k-way merges across multiple ATS partners.

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

Practice these live with InterviewChamp.AI →