Skip to main content

21. Merge Two Sorted Lists

easyAsked at Hugging Face

Merge two sorted linked lists into one sorted list. Hugging Face uses this to test the merge step of merge sort — a fundamental primitive for combining ranked model outputs or merging sorted inference result streams in distributed ML serving pipelines.

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

Source citations

Public interview reports confirming this problem appears in Hugging Face loops.

  • Glassdoor (2026-Q1)— Listed in Hugging Face SWE interview feedback as a standard linked-list manipulation problem.
  • Blind (2025-10)— Hugging Face interview threads note this as a common warm-up before the Merge K Sorted Lists hard variant.

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 value while preserving sorted order.

Example 2

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

Explanation: Both empty — return empty list.

Example 3

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

Explanation: One empty list — return the other.

Approaches

1. Iterative with dummy head

Use a dummy sentinel node as the start of the result. Advance a tail pointer, always picking the smaller of the two current nodes.

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

Tradeoff: O(1) space, clean loop. The dummy head eliminates the need to special-case the first insertion. Always preferred over recursive for production code.

2. Recursive

Recurse: if list1.val <= list2.val, list1.next = merge(list1.next, list2). Otherwise flip.

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 and concise, but O(m+n) stack depth. For very long lists this can stack-overflow. Mention the iterative version as safer in production.

Hugging Face-specific tips

Hugging Face often follows this with the K-sorted-lists variant, so mention the generalization: 'The two-list merge is the core primitive — for K lists, use a min-heap to pick the smallest current node across all K heads.' This signals you understand how hosted inference systems merge ranked results from multiple model shards. Also explain why the dummy head simplifies the code — no special case for the very first node.

Common mistakes

  • Forgetting to append the remaining non-null list after the while loop — always do tail.next = list1 || list2.
  • Creating new nodes instead of splicing existing ones — the problem says 'splice together the nodes'.
  • Not handling the case where one or both lists are empty.
  • In the recursive version, forgetting the base cases for null lists.

Follow-up questions

An interviewer at Hugging Face may pivot to one of these next:

  • Merge K Sorted Lists (LC 23) — use a min-heap to generalize to K lists in O(n log k).
  • Sort a Linked List (LC 148) — requires merge sort, which uses this merge step.
  • How would you merge K sorted streams of model inference results arriving in real time?

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 removes the special case for the first insertion. Without it you'd need an if/else to initialize the result head, and the loop body becomes more complex.

Does this create new nodes?

No — the nodes from list1 and list2 are reused; only their next pointers are rewired. O(1) extra space for the iterative approach.

What if both lists have equal values at the current position?

The condition list1.val <= list2.val handles ties by preferring list1, which is fine since the merged list just needs to be non-decreasing.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →