📖 8 min read
Last updated on

Merge Two Sorted Lists — Coding Interview Walkthrough

By intervu.dev

You’re in a coding interview. The interviewer says: “Merge two sorted linked lists into one sorted list.” You know this is an Easy problem. You also know that linked list pointer bugs are the most common reason candidates fail Easy problems under pressure. One forgotten current = current.next and the output is truncated. One wrong pointer advance and you’ve created a cycle.

This walkthrough covers both the iterative dummy-node approach and the recursive formulation, with every pointer mistake named and the ideal interview narrative spelled out.

The Problem

You are given the heads of two sorted linked lists, list1 and list2. Merge them into a single sorted linked list by splicing together the nodes of the two input lists (not creating new nodes). Return the head of the merged list. (LeetCode #21)

Example

Input list1 = [1,2,4], list2 = [1,3,4]

Output [1,1,2,3,4,4]

Both input lists are sorted in non-decreasing order. The merge compares front nodes, appends the smaller one, and advances that pointer. When one list is exhausted, the remaining nodes of the other are appended directly. No new nodes are created.

List 1: 1→2→4. List 2: 1→3→4. Merged result: 1→1→2→3→4→4.

Already comfortable with the solution? Practice it in a mock interview →

What Interviewers Are Actually Testing

Merge Two Sorted Lists tests fundamental linked list mechanics in a context where correctness depends on clean pointer management.

SkillWhat Interviewers Observe
Pointer mechanicsDo you advance pointers correctly without losing references or creating cycles?
Dummy node patternDo you use a sentinel head to avoid special-casing the first node insertion?
Loop terminationDo you correctly handle the tail attachment when one list is exhausted?
Recursive thinkingCan you model the problem as “pick the smaller head and recurse on the rest”?
Edge case handlingDo you handle one or both lists being empty?
Follow-up readinessCan you extend to merging k sorted lists or sorting a linked list?

Step 1: Clarifying Questions

  1. Are the lists sorted in ascending or descending order? Ascending (non-decreasing). Confirms your comparison direction.

  2. Can either list be empty? Yes. If list1 is None, the answer is list2, and vice versa.

  3. Should I create new nodes or reuse existing ones? Reuse. The problem says to splice together existing nodes.

  4. Can the lists contain duplicate values? Yes, duplicates are valid and should be preserved.

  5. What are the constraints on list lengths? Up to 50 nodes each. The correct solution is O(n + m) regardless.

Step 2: A First (Non-Optimal) Idea

The most naive approach: collect all values into an array, sort them, rebuild a linked list.

def mergeTwoLists(list1, list2):
    values = []
    while list1:
        values.append(list1.val)
        list1 = list1.next
    while list2:
        values.append(list2.val)
        list2 = list2.next

    values.sort()  # O(n log n)

    dummy = ListNode(0)
    current = dummy
    for v in values:
        current.next = ListNode(v)  # Creates new nodes — violates the intent
        current = current.next
    return dummy.next

This is O((n + m) log(n + m)) and creates new nodes instead of splicing. It throws away the fact that both lists are already sorted.

ApproachTimeSpace
Sort-based (naive)O((n+m) log(n+m))O(n + m)
Iterative merge (dummy node)O(n + m)O(1)
Recursive mergeO(n + m)O(n + m)

Step 3: The Key Insight

Both lists are already sorted. The next node in the merged result is always the smaller of the two current front nodes. A dummy sentinel node eliminates the special case of inserting the first node.

Two sorted lists merge in a single linear pass. Compare front nodes, attach the smaller one, advance that pointer. When one list runs out, attach the rest of the other directly.

The dummy node pattern eliminates head-insertion special-casing. Without it, the first assignment requires separate logic. With it, every insertion is current.next = node; current = current.next.

Recursive formulation: The merged list’s head is min(list1, list2). Its tail is the recursive merge of the remaining nodes. Base case: either list is None.

Step 4: Optimal Strategy (Iterative)

  1. Create a dummy sentinel node. Set current = dummy.
  2. While both list1 and list2 are non-None:
    • If list1.val <= list2.val, set current.next = list1 and advance list1.
    • Otherwise, set current.next = list2 and advance list2.
    • Advance current = current.next.
  3. Attach whichever list is non-exhausted: current.next = list1 if list1 else list2.
  4. Return dummy.next.

Python Implementation

Iterative — Dummy Node (Recommended for Interviews)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
    # Dummy sentinel node — avoids special-casing the first insertion
    dummy = ListNode(0)
    current = dummy  # Tracks the tail of the merged list

    while list1 and list2:
        if list1.val <= list2.val:
            current.next = list1   # Attach the smaller node
            list1 = list1.next     # Advance list1's pointer
        else:
            current.next = list2
            list2 = list2.next
        current = current.next     # Advance the merged list's tail

    # One list is exhausted — attach the remainder of the other
    current.next = list1 if list1 else list2

    return dummy.next  # Skip the sentinel, return the real head

Recursive — Elegant Alternative

def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
    # Base cases: if either list is exhausted, return the other
    if not list1:
        return list2
    if not list2:
        return list1

    # The smaller head becomes the next node in the merged list
    if list1.val <= list2.val:
        list1.next = mergeTwoLists(list1.next, list2)  # Recurse on list1's tail
        return list1
    else:
        list2.next = mergeTwoLists(list1, list2.next)  # Recurse on list2's tail
        return list2

Key implementation notes:

  • The dummy node’s value doesn’t matter. It’s a structural anchor, never part of the output.
  • current.next = list1 if list1 else list2 is the tail-attachment step. This single line handles both the case where list1 has remaining nodes and the case where list2 does.
  • In the recursive version, list1.next = mergeTwoLists(...) modifies the chosen node’s next pointer in place, splicing the lists without creating new nodes.
  • The recursive version uses O(n + m) stack space, one frame per node. For very long lists, this risks stack overflow. The iterative version uses O(1) space.

Time & Space Complexity

ApproachTimeSpace
Iterative (dummy node)O(n + m)O(1)
RecursiveO(n + m)O(n + m)

Time: Both approaches visit every node exactly once. Each visit does constant work. Total: O(n + m).

Space: Iterative uses only a fixed number of pointers, O(1). Recursive places one stack frame per call, O(n + m) total depth.

For interviews, the iterative approach is generally preferred for production-grade thinking. The recursive approach is elegant and worth presenting as an alternative, with its stack space tradeoff named explicitly.

Common Interview Mistakes

  1. Forgetting the tail-attachment step. When the loop exits, one list still has remaining nodes. Forgetting current.next = list1 if list1 else list2 truncates the output. The single most common bug.

  2. Not using a dummy node and struggling with head insertion. Without a sentinel, the first node requires special handling. The dummy node collapses initialization and loop logic into one path.

  3. Advancing the wrong pointer. After choosing list1.val, you must advance list1 = list1.next, not list2. Mixing these up corrupts the merged list.

  4. Creating a cycle by not advancing current. If you forget current = current.next, the tail never moves forward. The next iteration overwrites current.next, creating a cycle.

  5. Not discussing the recursive stack depth tradeoff. Presenting the recursive solution without mentioning O(n + m) stack space shows incomplete analysis.

  6. Skipping the trace-through. A quick trace on [1,3] + [2,4] catches pointer bugs before the interviewer does.

What a Strong Candidate Sounds Like

“Both lists are already sorted, so I never need to look beyond the front of each list. I’ll use an iterative approach with a dummy sentinel node to simplify head insertion.

I walk both lists simultaneously, compare their front values, and attach the smaller node to my result tail. When one list runs out, I attach the rest of the other directly.

Time is O(n + m), every node visited once. Space is O(1) for iterative. I can also do this recursively for cleaner code, but that uses O(n + m) stack space. I’ll go with iterative unless you’d prefer recursive.”

Example Interview Dialogue

Interviewer: Merge two sorted linked lists into one sorted list.

Candidate: Just to confirm: the lists are sorted ascending, I should reuse existing nodes, and either list could be empty?

Interviewer: Yes to all three.

Candidate: Since both lists are sorted, I only need to compare front nodes. I’ll use a dummy sentinel head so every insertion is uniform. I compare values, attach the smaller one as current.next, advance that list, advance current, and repeat until one list is empty. Then I attach the remaining list directly.

Interviewer: Why a dummy node instead of using list1 or list2 directly as the head?

Candidate: Without the dummy, I’d need a separate code path to establish the head before entering the loop. The dummy collapses that into a single loop body. It reduces surface area for bugs and is easier to reason about under pressure.

Interviewer: What’s the space complexity of a recursive solution?

Candidate: O(n + m) stack space because there’s one call frame per node. For very long lists, this could overflow the call stack. The iterative version avoids that with O(1) space.

Interviewer: How would you extend this to merge k sorted lists?

Candidate: That’s LeetCode #23. The optimal approach uses a min-heap seeded with the head of each list. Pop the smallest, append it, push that node’s next. Time is O(N log k) since the heap holds at most k elements.

Merge Two Sorted Lists is the foundation of a whole family of merge-based problems:

  • Merge k Sorted Lists (LeetCode #23). Extend to k lists using a min-heap. The most direct and important follow-up.
  • Sort List (LeetCode #148). Sort a linked list using merge sort, using this function as the merge step.
  • Merge Sorted Array (LeetCode #88). Same merge logic on arrays. Good for internalizing the two-pointer merge pattern.
  • Middle of the Linked List (LeetCode #876). Fast/slow pointer technique, foundational for merge sort on linked lists.
  • Add Two Numbers (LeetCode #2). Two-pointer traversal of two linked lists simultaneously.

Practice This in a Mock Interview

The dummy node technique and tail-attachment step feel logical and obvious when reading. But linked list problems have a specific failure mode under pressure: candidates lose track of which pointer they’re advancing, forget to move current forward, or miss the tail-attachment step entirely.

The pointer juggling that feels natural when reading becomes slippery when typing quickly with someone watching. The only way to build the muscle memory is to implement it from scratch, narrate the pointer state out loud, and trace through at least one example.

Start a mock interview for Merge Two Sorted Lists on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →