103. Merge Two Sorted Linked Lists

Why this mechanism works

This is the two-frontier sorted merge with links replacing array indices. A dummy tail gives every appended node the same attachment operation. Once one list ends, its partner's suffix is already sorted and can be attached with one link assignment.

State and boundaries

a and b are unread heads. tail is the last node of the committed sorted chain beginning at dummy.next.

Protocol

1. Compare unread heads while both exist.
2. Link the smaller head after tail.
3. Advance only that source.
4. Advance tail.
5. Attach the remaining suffix.
6. Return dummy.next.

Visualization

a: 1 -> 4 -> None
b: 2 -> 3 -> None
merged: dummy -> 1 -> 2 -> 3 -> 4

Python implementation

from structures import ListNode, build_list, list_values

def merge_lists(a, b):
    dummy = ListNode()
    tail = dummy
    while a is not None and b is not None:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a if a is not None else b
    return dummy.next

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 merge_lists: dummy = ListNode()
a=N1(val=1,next=N2,random=None); b=N3(val=2,next=N4,random=None); dummy=N5(val=0,next=None,random=None)

L5 merge_lists: tail = dummy
a=N1(val=1,next=N2,random=None); b=N3(val=2,next=N4,random=None); dummy=N5(val=0,next=None,random=None); tail=N5(val=0,next=None,random=None)

L8 merge_lists: tail.next, a = a, a.next
a=N2(val=4,next=None,random=None); b=N3(val=2,next=N4,random=None); dummy=N5(val=0,next=N1,random=None); tail=N5(val=0,next=N1,random=None)

L11 merge_lists: tail = tail.next
a=N2(val=4,next=None,random=None); b=N3(val=2,next=N4,random=None); dummy=N5(val=0,next=N1,random=None); tail=N1(val=1,next=N2,random=None)

L10 merge_lists: tail.next, b = b, b.next
a=N2(val=4,next=None,random=None); b=N4(val=3,next=None,random=None); dummy=N5(val=0,next=N1,random=None); tail=N1(val=1,next=N3,random=None)

L11 merge_lists: tail = tail.next
a=N2(val=4,next=None,random=None); b=N4(val=3,next=None,random=None); dummy=N5(val=0,next=N1,random=None); tail=N3(val=2,next=N4,random=None)

L10 merge_lists: tail.next, b = b, b.next
a=N2(val=4,next=None,random=None); b=None; dummy=N5(val=0,next=N1,random=None); tail=N3(val=2,next=N4,random=None)

L11 merge_lists: tail = tail.next
a=N2(val=4,next=None,random=None); b=None; dummy=N5(val=0,next=N1,random=None); tail=N4(val=3,next=None,random=None)

L12 merge_lists: tail.next = a if a is not None else b
a=N2(val=4,next=None,random=None); b=None; dummy=N5(val=0,next=N1,random=None); tail=N4(val=3,next=N2,random=None)

L4 merge_lists: dummy = ListNode()
a=None; b=N1(val=2,next=None,random=None); dummy=N2(val=0,next=None,random=None)

L5 merge_lists: tail = dummy
a=None; b=N1(val=2,next=None,random=None); dummy=N2(val=0,next=None,random=None); tail=N2(val=0,next=None,random=None)

L12 merge_lists: tail.next = a if a is not None else b
a=None; b=N1(val=2,next=None,random=None); dummy=N2(val=0,next=N1,random=None); tail=N2(val=0,next=N1,random=None)

Why the solution is correct

The smaller head is no greater than any unread value in either sorted list. Attaching it preserves sorted order and consumes one node. The remaining suffix can be attached after exhaustion because all its values follow the last committed frontier choice.

Time and space

O(n+m) time and O(1) auxiliary space beyond one dummy node; inputs are structurally consumed.

Common mistakes

Advancing a source before saving or attaching its node can lose it. Shared input nodes violate the node-disjoint precondition and can create unintended cycles.

Reasoning card

Transfer exercise

Merge k sorted linked lists with one heap entry per source, retaining a source identifier for equal values.