Merge Two Sorted Lists

The common failure mode here is treating linked lists like arrays: copy the values, sort them, and rebuild. That throws away the structure the problem gives you. The better model is simpler: repeatedly choose the smaller visible node and splice it into the result.

For this Merge Two Sorted Lists solution, I would start with an iterative merge using a dummy head and a tail pointer. It reuses every original node, handles the first-node edge case cleanly, and uses constant auxiliary space.

Read the Linked-List Contract

You receive the heads of two singly linked lists:

• Each list is already sorted in non-decreasing order.
• Either list may be empty.
• The result must contain every original node exactly once.
• The result must be formed by changing next pointers, not by creating replacement data nodes.
• You return the head of the merged list.

For example:

list1: 1 → 2 → 4
list2: 1 → 3 → 4

result: 1 → 1 → 2 → 3 → 4 → 4

There are three separate correctness obligations:

1. Order: the result is sorted.
2. Reachability: no original node is lost or duplicated.
3. Head selection: the returned pointer is the first real node in the result.

A brute-force approach could copy all values into an array, sort the array, and build a new list. That can produce the right sequence of values, but it ignores the supplied ordering and violates the intended in-place splicing model. The useful structure is already present. We only need to connect it.

See the Two Sorted Frontiers

At any point, each input list has a current node that has not yet been merged:

list1 → current node of list1
list2 → current node of list2

These two current nodes are the frontiers. Because each list is sorted, the smallest remaining node in either list must be one of those two frontier nodes.

That gives the greedy choice:

1. Compare list1.val and list2.val.
2. Select the smaller node.
3. Attach that existing node to the merged result.
4. Advance the pointer for the list you selected from.
5. Repeat.

If the values are equal, either node can go first. I use <= so that list1 wins ties consistently. The tie rule does not remove either node; it only chooses their order.

The working state has clear ownership:

• list1 points to the unmerged suffix of the first input.
• list2 points to the unmerged suffix of the second input.
• tail points to the final node in the merged prefix.

That distinction matters. tail does not scan ahead. It marks where the next chosen node will be attached.

Build the Invariant with a Dummy Head

The first real node creates an annoying special case: before the first attachment, there is no previous result node whose next pointer you can update.

A dummy node removes that branch.

dummy → None
tail  → dummy

The dummy node is temporary. It is not part of the returned list. The actual result begins at dummy.next.

The key invariant is:

The chain from dummy.next through tail is sorted, contains exactly the nodes selected so far, and tail is its last node. list1 and list2 point to the remaining unmerged suffixes.

Each iteration preserves that invariant through a careful pointer sequence.

Suppose list1.val <= list2.val. The safe sequence is:

chosen = list1
list1 = list1.next
tail.next = chosen
tail = chosen

Why advance list1 before attaching chosen? Because chosen.next still points into the unmerged suffix. We need to remember that successor before changing the ownership of the node in the result chain.

You can also write the common compact version:

tail.next = list1
list1 = list1.next
tail = tail.next

The same idea is happening, but the named chosen version makes pointer ownership easier to inspect while learning.

When one list becomes empty, stop comparing. The remaining list is already sorted. Every node in it is at least as large as the last selected node, so attach the entire remaining suffix:

tail.next = list1 if list1 is not None else list2

This is the main leverage in the problem. We do not walk through the leftover nodes one by one because their internal links are already correct.

Prove the Greedy Choice

The algorithm is greedy, but the proof is short because the input structure does most of the work.

Initialization

Before selecting any nodes, the merged real prefix is empty. The invariant holds vacuously:

• It is sorted.
• It contains no incorrect nodes.
• tail is the dummy node.
• Both input pointers still represent their complete lists.

Maintenance

Assume the invariant holds before an iteration.

Each remaining list is sorted. Therefore, every unmerged node in list1 is greater than or equal to list1.val, and every unmerged node in list2 is greater than or equal to list2.val.

The smaller of the two frontier values is therefore safe to place next. No hidden node behind either frontier can be smaller than its own current head.

After attaching that frontier node:

• The merged prefix remains sorted.
• The selected node is removed from exactly one unmerged suffix.
• tail advances to the new final node.

Every iteration consumes one node, so the loop makes progress and cannot stall.

Termination

The loop ends when at least one input pointer is empty. The other pointer represents a sorted suffix. Since all of its values are no smaller than the last value already attached, connecting that suffix directly preserves sorted order.

Equal values need no separate algorithm. If both frontiers contain 4, selecting either one first still leaves the other 4 reachable and ready to be attached later.

Dry-Run: Links and Frontiers

Use:

list1: 1 → 2 → 4
list2: 1 → 3 → 4

The table tracks the merged prefix after each selection. tail is the last real node in that prefix.

Step	list1 frontier	list2 frontier	Selected	Merged prefix
Start	1	1	—	empty
1	2	1	list1's 1	1
2	2	3	list2's 1	1 → 1
3	2	3	list1's 2	1 → 1 → 2
4	4	3	list2's 3	1 → 1 → 2 → 3
5	4	4	list1's 4	1 → 1 → 2 → 3 → 4
6	empty	4	list2's 4	1 → 1 → 2 → 3 → 4 → 4

At step 6, list1 is empty. There is no reason to compare again. Attach list2's remaining suffix directly.

The empty cases follow naturally:

list1: empty
list2: empty
result: empty

The dummy node's next remains None.

list1: empty
list2: 2 → 5
result: 2 → 5

The loop never runs, and the remaining list is attached immediately.

The most common pointer mistakes are predictable:

• Lose the successor: rewire a chosen node before saving or advancing past its original next.
• Return the dummy: return dummy.next, not dummy.
• Drop the suffix: after the loop, connect tail.next to whichever list is non-empty.
• Copy values: creating replacement nodes solves a different problem and hides whether you preserved node identity.
• Collapse duplicates: equal values are separate nodes. Select one, then select the other later.

Read the link. Trace the state. Fix the assumption.

Implement the Iterative Python Solution

Assume the usual node interface:

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

Here is the iterative implementation:

from typing import Optional


class Solution:
    def mergeTwoLists(
        self,
        list1: Optional[ListNode],
        list2: Optional[ListNode],
    ) -> Optional[ListNode]:
        dummy = ListNode()
        tail = dummy

        while list1 is not None and list2 is not None:
            if list1.val <= list2.val:
                chosen = list1
                list1 = list1.next
            else:
                chosen = list2
                list2 = list2.next

            tail.next = chosen
            tail = chosen

        # One list is empty; append the other sorted suffix.
        tail.next = list1 if list1 is not None else list2

        return dummy.next

Each variable answers a specific obligation:

• list1 and list2 identify the two remaining sorted frontiers.
• chosen identifies the existing node being transferred.
• tail identifies the only link that needs to be extended.
• dummy.next identifies the first real result node.

The assignment order is the important part:

1. Save the chosen node.
2. Advance the source list pointer.
3. Attach the chosen node.
4. Move tail.

The code does not allocate a node for every input value. It changes the links between the nodes already provided.

Derive the Recursive Version

The same frontier decision can be expressed recursively.

If either list is empty, the answer is the other list unchanged. Otherwise, select the smaller head. That node becomes the result head, and its next pointer receives the merge of the remaining suffix with the other list.

from typing import Optional


class Solution:
    def mergeTwoLists(
        self,
        list1: Optional[ListNode],
        list2: Optional[ListNode],
    ) -> Optional[ListNode]:
        if list1 is None:
            return list2
        if list2 is None:
            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 recurrence is:

merge(list1, list2)
  = list1 followed by merge(list1.next, list2), if list1.val <= list2.val
  = list2 followed by merge(list1, list2.next), otherwise

The base case is exactly the exhaustion rule from the iterative solution. When one suffix is empty, return the other suffix.

Recursion mirrors the proof naturally: choose one safe frontier, then solve the same problem on a smaller pair of suffixes. I still prefer the iterative version in interviews when stack usage and pointer visibility matter. It keeps all state in front of you and uses constant auxiliary space beyond the dummy node and a few pointers.

Both versions process each input node once. The recursive version uses call-stack space proportional to the combined number of nodes. The iterative version does not grow its auxiliary state as the lists grow.

Complexity and Edge-Case Audit

Let n be the number of nodes in list1 and m the number of nodes in list2.

Time

The iterative algorithm compares and selects nodes while both lists remain. Each node is selected once or included in the final suffix attachment. Therefore, the total work is:

O(n + m)

The recursive version has the same time complexity because each recursive call consumes one node from one input list.

Space

The iterative method uses:

O(1) auxiliary space

That includes the dummy node and a fixed number of pointers. It does not include the input nodes, which are reused.

The recursive method uses:

O(n + m) call-stack space

in the longest recursive chain.

Before submitting, audit these cases:

• Both lists empty.
• Exactly one list empty.
• Negative values.
• Duplicate values, including equal values at both frontiers.
• One entire list preceding the other.
• Exhaustion of list1 first.
• Exhaustion of list2 first.
• Returning dummy.next, not the dummy node.
• Appending the remaining suffix after the comparison loop.
• Reusing existing nodes rather than creating replacement data nodes.
• Preserving every original node exactly once.

The broader recognition rule is worth keeping: when two structures expose sorted, comparable frontiers, repeatedly commit the smallest safe frontier. Preserve its successor before rewiring, state the invariant, and let exhaustion finish the job.

The durable skill is pointer ownership. After every mutation, you should be able to answer one question without hesitation: which pointer owns the next unprocessed node?