Merge Two Sorted Linked Lists

Merging sorted sequences is one of those building blocks that comes up far more often than you'd expect, merge sort, multi-shard result combining, database cursor merges.

Problem

Given two sorted singly-linked lists, merge them into a single sorted linked list by re-linking existing nodes (no new node allocation beyond a dummy head).

Input: heads of two sorted linked lists Output: head of the merged sorted list

Approach

Use a dummy head node to simplify edge cases. Walk both lists simultaneously:

1. Compare the current nodes of both lists.
2. Attach the smaller node to the merged list and advance that pointer.
3. When one list is exhausted, attach the remainder of the other, it's already sorted.

No extra nodes are created; we're just rewiring .next pointers.

Implementation

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

    def __repr__(self):
        return f"{self.val} -> {repr(self.next)}"


def merge_two_lists(l1, l2):
    dummy = ListNode()
    current = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    current.next = l1 or l2
    return dummy.next


# Quick test
l1 = ListNode(0)
l1.next = ListNode(1)

l2 = ListNode(2)
l2.next = ListNode(3)

print(merge_two_lists(l1, l2))
# 0 -> 1 -> 2 -> 3 -> None

Complexity

• Time: O(n + m) where n and m are the lengths of the two lists
• Space: O(1), only pointer manipulation, no auxiliary storage

Takeaway

The two-pointer merge generalizes to k-way merges with a min-heap. Once you have that, merging sorted database cursors or combining ranked candidate lists from multiple sources is the same idea.

---

Back to Algorithms & Data Structures