How to Explain Merge Two Sorted Linked Lists in a Coding Interview (Step-by-Step)

Merge Two Sorted Lists is the canonical linked list problem — and the one most likely to expose gaps in pointer fundamentals. The algorithm is simple, but candidates consistently struggle to articulate why a dummy head node is used, what happens when one list runs out, and how to avoid losing track of the merged list’s head.

In this post, you’ll learn exactly how to walk an interviewer through LeetCode 21: the dummy head technique, the iterative compare-and-link loop, the tail-append optimisation for the remaining list, and the elegant recursive solution as a follow-up.

Problem Statement

Examples

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

What Is the Problem?

“I’m given two already-sorted linked lists and need to weave them together into a single sorted list — by relinking existing nodes, not creating new ones. The key challenge isn’t the comparison logic; it’s managing pointers carefully so I never lose the head of the merged list or orphan a node.”

Emphasising “relinking existing nodes” signals that you understand memory constraints — you’re not allocating new node objects, just redirecting next pointers. That’s the kind of precision interviewers look for on linked list problems.

Step 1: Compare Approaches Before Jumping to Code

“I’ll walk through the iterative solution as the primary answer — it’s O(1) space and avoids stack overflow risk on long lists. I can then show the recursive version as an elegant alternative if the interviewer wants both.”

The Key Insight — Always Pick the Smaller Head

“Without a dummy head, I’d need a conditional to handle ‘what if the merged list is empty when I try to append?’ The dummy node eliminates that check entirely — tail always points to a valid node and tail.next = node always works.”

The Dummy Head Technique

Step 2: Explain the Algorithm in Plain English

Step-by-Step Visual — list1=[1→4→5], list2=[1→3→4]

Blue = list1 nodes, Purple = list2 nodes, Orange = nodes added to the result so far.

Step 3: Talk Through the Iterative Code

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)   # Sentinel — avoids special-casing the head
        tail  = dummy

        while list1 and list2:
            if list1.val <= list2.val:
                tail.next = list1          # Link the smaller node
                list1     = list1.next     # Advance list1
            else:
                tail.next = list2
                list2     = list2.next
            tail = tail.next               # Advance the merged tail

        # Append whichever list still has nodes — O(1), not a loop
        tail.next = list1 if list1 else list2

        return dummy.next                  # Skip the dummy sentinel

Three details worth narrating: (1) tail.next = list1 relinks the existing node — no new allocation; (2) tail = tail.next must come after the assignment, not before; (3) tail.next = list1 if list1 else list2 replaces an entire loop — the remaining nodes are already sorted and already linked, so one pointer assignment appends all of them.

The Recursive Solution — Elegant Alternative

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # Base cases: if either list is empty, return the other
        if not list1: return list2
        if not list2: return list1

        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

"The recursive version is O(n+m) time and O(n+m) space due to the call stack. For this problem's constraints (max 50 nodes each) it's perfectly fine. If asked to handle arbitrarily long lists, the iterative approach is strictly better."

Step 4: Highlight Edge Cases

Step 5: State Time and Space Complexity

"Both approaches are O(n+m) time — every node is touched exactly once. The difference is space: iterative uses O(1) extra memory (just the dummy node and two pointers); recursive uses O(n+m) stack frames. For the problem's constraint of 50 nodes each, both are fine. For general use, iterative is the safer production choice."

Interview Checklist for Merge Two Sorted Linked Lists

• Restate — "weave two sorted lists by relinking nodes, not creating new ones"
• Mention the collect-into-array approach and explain why it wastes the sorted property
• Name and explain the dummy head technique — why it removes the head-initialisation special case
• Describe the tail pointer — it always points to the last node of the merged result
• Use <= not < for the comparison — handles equal values correctly
• Explain the tail-append at the end — one pointer assignment, not a loop
• Return dummy.next, not dummy
• Offer the recursive solution and state the O(n+m) stack space tradeoff
• Call out edge cases: both empty, one empty, one list fully smaller, duplicates
• State O(n+m) time and O(1) space for iterative; O(n+m) space for recursive

Related Problems to Practice

If you can solve Merge Two Sorted Lists cleanly, try these next: