Merge Two Sorted Lists

Bài toán

Cho hai danh sách liên kết đã được sắp xếp tăng dần list1 và list2. Hãy trộn (merge) chúng lại thành một danh sách liên kết mới cũng được sắp xếp tăng dần.

Ví dụ:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Phân Tích & Tiếp Cận

Iterative (Dùng Dummy Node)

Mẹo quan trọng nhất khi làm việc với Linked List là sử dụng Dummy Node (Node giả). Nó giúp ta tránh phải xử lý trường hợp biên "head chưa tồn tại". Ta cứ gắn mọi thứ vào sau dummy, cuối cùng trả về dummy.next.

Quy trình:

1. Tạo dummy node. Con trỏ tail trỏ vào dummy.
2. So sánh đầu của list1 và list2.
3. Bên nào bé hơn thì gắn vào sau tail. Sau đó tiến con trỏ của bên đó lên.
4. Lặp lại cho đến khi một bên hết.
5. Gắn phần thừa còn lại của bên chưa hết vào sau tail.

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    const dummy = new ListNode(0);
    let tail = dummy;

    while (list1 && list2) {
        if (list1.val < list2.val) {
            tail.next = list1;
            list1 = list1.next;
        } else {
            tail.next = list2;
            list2 = list2.next;
        }
        tail = tail.next;
    }

    // Gắn phần còn dư (nếu có)
    if (list1) {
        tail.next = list1;
    } else if (list2) {
        tail.next = list2;
    }

    return dummy.next;
}

• Time Complexity: $O(n + m)$.
• Space Complexity: $O(1)$. Ta chỉ thay đổi các mối nối (pointers), không tạo node mới (trừ dummy).

Pattern Nhận Diện

Kỹ thuật Dummy Node cực kỳ hữu dụng cho các bài toán xây dựng List mới từ List cũ (Merge, Filter, Partition). Kỹ thuật Zipper (so sánh 2 đầu, lấy 1, tiến 1) cũng là nền tảng của thuật toán Merge Sort.