Skip to main content

21. Merge Two Sorted Lists

easyAsked at DRW

DRW uses Merge Two Sorted Lists as a building block — it is the O(n+m) merge step inside merge-sort, inside merge-k-sorted-lists, inside order-book consolidation. Get this right cleanly and quickly; interviewers use it to see pointer discipline before escalating to the k-way variant.

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

Source citations

Public interview reports confirming this problem appears in DRW loops.

  • Glassdoor (2025-Q4)— DRW SWE candidates report linked-list merge as a phone-screen warm-up before being asked about k-way sorted merges in the same session.
  • Blind (2025-09)— DRW interview threads frequently cite merge-two-lists as a prerequisite question leading directly to Merge K Sorted Lists in onsite rounds.

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: Both empty.

Example 3

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

Explanation: One empty list.

Approaches

1. Iterative with dummy head

Use a dummy head node to avoid null-checking on the first insertion. Walk both lists simultaneously, appending the smaller node to the result. Append the remaining tail.

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

Tradeoff: O(n+m) time, O(1) space. The dummy head eliminates edge-case handling for the first node. This is the canonical solution DRW expects.

2. Recursive

Recursively select the smaller head and attach the merged result of the remaining lists. Clean and readable but O(n+m) stack space.

Time
O(n+m)
Space
O(n+m) 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 but uses O(n+m) stack space — problematic for very long lists and disqualifying at DRW where memory budgets are tight. Present iterative first.

DRW-specific tips

Code the iterative version without hesitation, then explain: 'This is the merge step in merge sort — O(n+m) with O(1) space. The k-way generalization replaces the two-pointer comparison with a min-heap over k list heads.' DRW interviewers will ask the k-way version immediately after. Also: 'How would you merge two sorted arrays in-place without extra memory?' — backward merge from the end of the combined array.

Common mistakes

  • Forgetting the dummy head and wrestling with null checks for the first node.
  • Not appending the remaining tail after the while loop exits — one list may still have nodes.
  • Using <= instead of < and not thinking about stability — equal elements should preserve original order (take from list1 first for stability).
  • Choosing recursion without flagging the stack-depth cost for large lists.

Follow-up questions

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

  • Merge K Sorted Lists (LC 23) — generalize to k lists using a min-heap.
  • Sort List (LC 148) — sort a linked list in O(n log n) time and O(1) space using merge sort.
  • How would you merge two sorted arrays in O(n+m) time and O(1) extra space?

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 special case of inserting the first node into an empty result list. Every insertion uses the same curr.next = node pattern.

Is stability important here?

For equal values, always take from list1 first (<=). This preserves the relative order of equal elements — a requirement in stable merge sort and important for order-book tie-breaking by time priority.

Why does DRW treat this as a stepping stone?

Merge K Sorted Lists uses this exact merge operation inside a heap-based loop. If you can't code two-way merge cleanly in two minutes, you won't get to the k-way version.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →