Skip to main content

21. Merge Two Sorted Lists

easyAsked at Juniper Networks

Merge two sorted linked lists into one sorted list. Juniper asks this because merging sorted sequences is fundamental to external-merge-sort of routing table dumps, ordered BGP prefix lists, and priority-ordered packet queues — all real artifacts in networking OS development.

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

Source citations

Public interview reports confirming this problem appears in Juniper Networks loops.

  • Glassdoor (2025-Q4)— Cited in Juniper SWE interview summaries as a standard linked-list merge warm-up.
  • Blind (2025-10)— Juniper prep threads list merge-two-sorted-lists as a common linked-list problem at all levels.

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: Interleave nodes in sorted order.

Example 2

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

Explanation: Two empty lists merge to an 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 to simplify pointer logic. Walk both lists, appending the smaller node each step.

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 nodes
  return dummy.next;
}

Tradeoff: O(m+n) time, O(1) space. The dummy head eliminates the edge case of building the result head. Preferred by Juniper — simple, correct, and efficient.

2. Recursive

Recursively pick the smaller head and attach the merged tail.

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: Clean to read but O(m+n) stack depth. Juniper will ask you to convert to iterative to avoid stack overflow on long lists.

Juniper Networks-specific tips

Use a dummy head — it is a standard technique in Juniper's linked-list problems that makes the return statement trivial (always dummy.next). Connect this to the k-way merge used in Merge K Sorted Lists, which Juniper also commonly asks as a follow-up. Explain that at the end of the loop you can safely attach the non-null remainder in O(1) because both input lists are already sorted.

Common mistakes

  • Not attaching the remaining tail — when one list is exhausted, the rest of the other list needs to be appended.
  • Forgetting the null-list base cases — an empty list should return the other list.
  • Creating new nodes instead of re-linking existing ones — the problem says splice existing nodes, not copy values.
  • Not using a dummy head — then the first-node assignment requires special handling.

Follow-up questions

An interviewer at Juniper Networks may pivot to one of these next:

  • Merge K Sorted Lists (LC 23) — use a min-heap or divide and conquer.
  • Sort a linked list (LC 148) — merge sort applied to a linked list.
  • How would you merge two sorted arrays in-place?

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?

It removes the need to handle the empty-result edge case separately. You always return dummy.next which is null if both lists are empty.

Is it safe to attach the remaining tail directly?

Yes — the remaining portion is already sorted and there are no more comparisons needed. A single pointer assignment appends it in O(1).

Why does the recursive version use O(m+n) stack space?

Each recursive call processes one node, so the depth equals the total number of nodes across both lists.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →