Skip to main content

21. Merge Two Sorted Lists

easyAsked at Broadcom

Merge two sorted linked lists into one sorted list. Broadcom asks this because the merge step of merge sort appears directly in multi-queue packet scheduling algorithms used in Broadcom's network switch ASICs — merging sorted priority queues is a real hardware concern.

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

Source citations

Public interview reports confirming this problem appears in Broadcom loops.

  • Glassdoor (2025-12)— Cited in Broadcom SWE onsite reports as a linked-list fundamentals question.
  • Blind (2025-09)— Broadcom infrastructure candidates report this problem in the second coding round alongside graph problems.

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. Return the head of the merged linked list.

Constraints

  • The number of nodes in both lists is in the range [0, 50].
  • −100 <= Node.val <= 100.
  • Both list1 and list2 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]

Explanation: Nodes are interleaved by comparing values at each step.

Example 2

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

Explanation: Both empty — return null.

Example 3

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

Explanation: One empty — return the other.

Approaches

1. Iterative with dummy head

Use a dummy node as the merged list's head sentinel. Walk both lists simultaneously, always attaching the smaller node to the result, then append the remaining tail.

Time
O(m + n)
Space
O(1)
function mergeTwoLists(list1, list2) {
  const dummy = { next: null };
  let curr = dummy;
  while (list1 !== null && list2 !== null) {
    if (list1.val <= list2.val) {
      curr.next = list1;
      list1 = list1.next;
    } else {
      curr.next = list2;
      list2 = list2.next;
    }
    curr = curr.next;
  }
  curr.next = list1 !== null ? list1 : list2;
  return dummy.next;
}

Tradeoff: O(m+n) time, O(1) space. Splices existing nodes without allocating new memory — the correct approach in memory-constrained driver environments.

2. Recursive

At each call, pick the smaller head and recurse on the remaining tail. Base case: either list is null.

Time
O(m + n)
Space
O(m + n) call stack
function mergeTwoLists(list1, list2) {
  if (list1 === null) return list2;
  if (list2 === null) return list1;
  if (list1.val <= list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  } else {
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
  }
}

Tradeoff: Elegant but O(m+n) stack depth. Mention the stack risk if lists are large — relevant to embedded Broadcom contexts.

Broadcom-specific tips

At Broadcom, lead with the iterative dummy-node approach and state: 'I'm reusing existing nodes to avoid allocation — important in a kernel or firmware setting.' The dummy head eliminates the need to special-case the first node. Broadcom follows up with Merge K Sorted Lists, so mentally note that this two-list merge is the building block for that heap-based solution.

Common mistakes

  • Allocating new nodes instead of splicing existing ones — wastes memory and misses the O(1) space opportunity.
  • Forgetting to append the remaining tail after the while loop.
  • Not handling both lists being empty before starting.
  • Advancing both pointers in the same iteration — only advance the one you just attached.

Follow-up questions

An interviewer at Broadcom may pivot to one of these next:

  • Merge K sorted lists using a min-heap (LC 23).
  • Sort a linked list using merge sort (LC 148).
  • How would you merge two sorted lists stored on different machines (distributed merge)?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why use a dummy head node?

It eliminates the special case of initialising the merged list's first node. Every attachment becomes a uniform curr.next = node operation.

Does the order of the <= comparison matter?

Using <= (not <) ensures stability — equal nodes from list1 appear before list2, preserving relative order.

What if the lists are unsorted?

You'd need to sort them first — O(n log n) — then merge. The problem guarantees sorted input, so the O(m+n) merge suffices.

Practice these live with InterviewChamp.AI

Drill Merge Two Sorted Lists and other Broadcom interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →