Skip to main content

21. Merge Two Sorted Lists

easyAsked at Goldman Sachs

Merge two sorted linked lists into one sorted list. Goldman Sachs uses Merge Two Sorted Lists to test the dummy-node pattern — the canonical trick that simplifies head-handling and pointer rewiring.

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

Source citations

Public interview reports confirming this problem appears in Goldman Sachs loops.

  • Glassdoor (2026-Q1)— Goldman Sachs SWE phone-screen reports list Merge Two Sorted Lists as a standard warm-up before Merge K Sorted.
  • LeetCode Discuss (2025-11)— Merge Two Sorted Lists is in the top-15 of LeetCode's Goldman Sachs company tag.

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]

Example 2

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

Example 3

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

Approaches

1. Dummy-node iterative merge (optimal)

Allocate a dummy head. Walk both lists; at each step splice the smaller node onto the tail of the result. Append any remaining list at the end.

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

Tradeoff: Linear time, O(1) extra space (we reuse existing nodes). The dummy node eliminates the 'is this the first node?' branch — Goldman wants to see this pattern.

2. Recursive

merge(a, b) returns the smaller head with .next = merge(of the rest).

Time
O(n + m)
Space
O(n + m)
function mergeTwoListsRec(l1, l2) {
  if (!l1) return l2;
  if (!l2) return l1;
  if (l1.val <= l2.val) {
    l1.next = mergeTwoListsRec(l1.next, l2);
    return l1;
  }
  l2.next = mergeTwoListsRec(l1, l2.next);
  return l2;
}

Tradeoff: Cleaner to write but O(n+m) call stack. Mention it as the elegant version, but lead with iterative for production-grade memory.

Goldman Sachs-specific tips

Goldman Sachs interviewers want to see the dummy-node trick named explicitly. Without the dummy, you need a separate branch to determine the head of the result list — with it, the loop is uniform. The 'tail.next = list1 || list2' one-liner at the end handles the leftover and is elegant; if Goldman sees you doing two more loops you'll get marked for inefficiency.

Common mistakes

  • Allocating new nodes for the result instead of splicing existing nodes — works but uses O(n+m) extra space.
  • Forgetting to advance the tail pointer after splicing.
  • Skipping the leftover-append at the end, which truncates the result at the first list's exhaustion.

Follow-up questions

An interviewer at Goldman Sachs may pivot to one of these next:

  • Merge K Sorted Lists (LC #23) — use a min-heap of (val, list_index) for O(N log k).
  • Merge two sorted ARRAYS in-place (LC #88) — walk from the back to avoid overwriting.
  • Stable merge — the dummy-node version is already stable by using <= comparison.

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 <= and not <?

Stability. With <=, when values are equal, list1's node is spliced first — this preserves the relative order from the input lists. Use < and the order can flip for equal values. Goldman's senior rounds sometimes ask 'is your merge stable?' to check.

Do I need to handle the cycle case?

No — input lists are assumed acyclic. If the interviewer adds 'what if input might be cyclic?', that's a different question (Floyd's cycle detection first, then refuse to merge if either is cyclic).

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →