Skip to main content

21. Merge Two Sorted Lists

easyAsked at Akamai

Merge two sorted linked lists into one sorted list. Akamai asks this because merge is a fundamental building block for external sort — the same pattern used to merge sorted access logs from thousands of edge servers into a single chronological stream.

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

Source citations

Public interview reports confirming this problem appears in Akamai loops.

  • Glassdoor (2025-12)— Mentioned in Akamai SWE interview reports as a standard linked list question in first-round coding sessions.
  • Blind (2025-09)— Akamai candidates note merge-based linked list problems appear regularly in phone screens.

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: Interleaved by value comparison at each step.

Example 2

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

Explanation: Both empty — return empty.

Example 3

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

Explanation: One empty list — return the other.

Approaches

1. Iterative with dummy head

Create a dummy sentinel node. Use a tail pointer to build the merged list by always attaching the smaller of the two current nodes. After the loop, attach whichever list still has remaining 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(m+n) time, O(1) space. The dummy head eliminates the special case of an empty merged list. This is the standard answer Akamai expects.

2. Recursive

At each call, pick the smaller head and recurse on the remainder.

Time
O(m + n)
Space
O(m + n) 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 but O(m+n) stack depth. Fine for small lists, but the iterative version is preferred when discussing production code at scale.

Akamai-specific tips

This problem generalizes to Merge K Sorted Lists — mention it proactively. 'Two-way merge is the base case; for K lists I would use a min-heap to pull the global minimum in O(log K) per step.' Akamai interviewers prize forward-thinking candidates who connect individual problems to system-level building blocks.

Common mistakes

  • Not handling the case where one list is exhausted — must attach the remaining tail of the other list.
  • Forgetting to advance tail after each attachment — creates an infinite loop.
  • Returning dummy instead of dummy.next — dummy is the sentinel, not a real node.

Follow-up questions

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

  • Merge K Sorted Lists (LC 23) — extend to K lists using a min-heap.
  • Sort List (LC 148) — sort a linked list in O(n log n) using merge sort.
  • How would you merge K sorted streams arriving in real time without buffering all of them?

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 eliminates the null-check for initializing the merged list head. Without it, you'd need an if-block to set the first node, then continue the loop — the dummy makes every iteration uniform.

Do we need to create new nodes?

No. We rewire the existing nodes' next pointers. No allocations means O(1) extra space.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →