Skip to main content

21. Merge Two Sorted Lists

easyAsked at HP

HP's device-driver and print-spooler stacks frequently merge ordered queues of pending jobs from multiple input sources. Merging two sorted linked lists is the fundamental building block — HP uses it to verify that candidates handle pointer manipulation without losing data.

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

Source citations

Public interview reports confirming this problem appears in HP loops.

  • Glassdoor (2025-Q4)— HP SWE onsite feedback cites Merge Two Sorted Lists as a standard linked-list question in first technical rounds.
  • Blind (2025-09)— HP prep threads consistently include Merge Two Sorted Lists as a must-know easy question for systems-software roles.

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 spliced in sorted order without allocating new nodes.

Example 2

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

Explanation: Both lists empty; result is empty.

Example 3

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

Explanation: One empty list — return the other.

Approaches

1. Iterative with dummy head

Use a dummy head node to avoid special-casing the first element. Walk both lists simultaneously, attaching the smaller node to the result. Attach any remaining tail.

Time
O(m + n)
Space
O(1)
function mergeTwoLists(list1, list2) {
  const dummy = { val: 0, 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; // attach remaining
  return dummy.next;
}

Tradeoff: O(1) extra space (the dummy node is a single allocation). Clean and easy to follow. The dummy head eliminates the edge case of an empty initial result list.

2. Recursive

Compare the heads of both lists. Recurse on the smaller head, letting the call stack build the merged list.

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) call stack. HP's systems context favors iterative for robustness; use recursive only if asked explicitly.

HP-specific tips

Draw the pointer-rewiring diagram before coding — HP interviewers want to see you reason about pointer safety. The dummy head pattern eliminates null-checks at the start and is a broadly reusable pattern in linked-list problems. Mention that in a real job-queue context you'd need thread-safety, which sets up a strong follow-up conversation.

Common mistakes

  • Not attaching the remaining tail — if one list is exhausted first, the rest of the other list must be appended.
  • Allocating new nodes — the problem asks to splice existing nodes, not create new ones.
  • Forgetting to advance curr after each attachment — curr must follow the tail of the merged result.
  • Off-by-one when one list is initially empty — the dummy head handles this cleanly; without it, you need extra null checks.

Follow-up questions

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

  • Merge k sorted linked lists (LC 23) — use a min-heap or divide and conquer.
  • How would you merge two sorted doubly-linked lists in O(1) extra space?
  • How would you make the merge thread-safe for concurrent enqueue/dequeue operations?

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?

Without it, you must special-case the first assignment to the result head. With dummy, every iteration is uniform: curr.next = chosen_node; curr = curr.next.

Do you allocate new nodes?

No — you only rewire the .next pointers of the existing nodes. Memory allocation is O(1) (just the dummy node).

What if both lists have the same value at a step?

The condition list1.val <= list2.val is a stable tie-breaking rule — list1's node is chosen first. Either choice is correct; just be consistent and state your tie-breaking rule.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →