Linked Lists

Merge Two Sorted Lists

TimeO(n + m) SpaceO(1)

Imagine merging two sorted stacks of papers. You look at the top paper of each stack, take whichever is smaller, and place it on your output pile. Repeat until both stacks are empty. Simple, fast, and the output is perfectly sorted.

When to use it: Combining two sorted sequences — the merge step of merge sort, merging k sorted lists, or combining sorted streams.

Key insight: Since both lists are already sorted, you always compare only the two front elements. The dummy head trick avoids special-casing the first node.

Common trap: Forgetting to attach the remaining tail. When one list is exhausted, just link the rest of the other list — don’t iterate through it node by node.

function mergeTwoLists(l1, l2):
    dummy = new Node(0)             # dummy head to simplify logic
    current = dummy

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

    # Attach the remaining non-empty list
    if l1 != null:
        current.next = l1
    else:
        current.next = l2

    return dummy.next               # skip the dummy node

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


def merge_two_lists(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
    dummy = ListNode(0)
    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


def merge_k_lists(lists: list[ListNode | None]) -> ListNode | None:
    """Merge k sorted lists using divide and conquer."""
    if not lists:
        return None
    if len(lists) == 1:
        return lists[0]

    mid = len(lists) // 2
    left = merge_k_lists(lists[:mid])
    right = merge_k_lists(lists[mid:])

    return merge_two_lists(left, right)

Problem: You are given k sorted linked lists. Merge them into one sorted linked list.

How would you approach this?

Answer: This is merge two sorted lists scaled up with divide and conquer. Pair up the k lists and merge each pair, reducing k lists to k/2. Repeat log(k) times. Total: O(N log k) where N is total elements. Alternatively, use a min-heap of size k.

Problem: Given two sorted arrays, merge them into one sorted array in-place (the first array has enough space at the end).

How would you approach this?

Answer: This is the merge pattern but done from the back. Start filling from the end of the first array, comparing the largest remaining elements. This avoids overwriting elements that haven't been processed yet.

Time: O(n + m) where n and m are the lengths of the two lists. Each comparison advances one pointer, and we make at most n + m comparisons total before both lists are exhausted.

Space: O(1) because we rewire existing node pointers — no new nodes are created. The only extra memory is the dummy head node and the current pointer.