Merge Two Sorted Lists: thủ thuật dummy head

Có một phiên bản bài toán này không dùng dummy head. Tôi đã viết nó. Nó hoạt động, nhưng bạn phải xử lý đặc biệt cho node đầu tiên — xác định nên lấy từ list nào trước, gán result bằng node đó, rồi mới bắt đầu vòng lặp. Bảy hoặc tám dòng boilerplate trước khi logic thực sự bắt đầu. Dummy head cắt bỏ tất cả điều đó. Bạn bắt đầu với một node giả mà bạn sẽ không bao giờ trả về, cho current một thứ có thật để trỏ vào, và vòng lặp trở nên đồng nhất cho mọi bước kể cả bước đầu tiên.

Đó là toàn bộ thủ thuật. Nghe có vẻ nhỏ. Nhưng thực tế nó là sự khác biệt giữa code dễ sai và code khó sai.

Bài toán thực sự cho bạn gì

Hai singly linked list, cả hai đã được sắp xếp theo thứ tự không giảm. Hợp nhất chúng thành một list đã sắp xếp bằng cách nối lại các node hiện có — không tạo node mới, chỉ chỉnh lại con trỏ next. Trả về head của list đã merge.

list1:  1 -> 2 -> 4 -> null
list2:  1 -> 3 -> 4 -> null

result: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> null

Constraints đáng đọc kỹ. Tối đa 50 node mỗi list, giá trị trong [-100, 100], cả hai list đã sắp xếp theo thứ tự không giảm. Số node nhỏ có nghĩa là không cần lo về độ sâu call stack cho giải pháp recursive (tối đa 100 frame). Giá trị âm không có gì đặc biệt — phép so sánh <= hoạt động đúng với số nguyên âm. Constraint thực sự dẫn dắt tất cả là đảm bảo thứ tự đã sắp xếp.

Không có đảm bảo đó, bạn sẽ merge rồi sort: O((m+n) log(m+n)). Với đảm bảo đó, bạn không bao giờ cần nhìn xa hơn một bước. Tại bất kỳ thời điểm nào, phần tử nhỏ nhất chưa xử lý đang nằm ở head của một trong hai list. So sánh hai head, lấy cái nhỏ hơn, tiến con trỏ đó. Khi một list cạn kiệt, gắn phần còn lại vào — nó đã được sắp xếp sẵn, nên kết nối trực tiếp bằng một phép gán con trỏ duy nhất.

Chính đảm bảo sorted-order đó là thứ làm O(m+n) time trở nên khả thi, và đó là insight phân biệt merge với sort-then-merge.

Giải pháp iterative với dummy head

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        dummy = ListNode(0)
        current = dummy
 
        while list1 and list2:
            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next
 
        current.next = list1 or list2
 
        return dummy.next

public class Solution {
    public ListNode MergeTwoLists(ListNode list1, ListNode list2) {
        var dummy = new ListNode(0);
        var current = dummy;
 
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }
 
        current.next = list1 ?? list2;
 
        return dummy.next;
    }
}

Mỗi iteration của vòng lặp làm ba việc: chọn head nhỏ hơn, gắn nó vào, tiến lên. Dòng current = current.next ở cuối là quan trọng — nếu không có nó, current sẽ mãi trỏ vào cùng một node và mỗi lần gán sau sẽ ghi đè current.next mà không xây được chain.

Phần gắn đuôi current.next = list1 or list2 hoạt động vì sau khi vòng lặp kết thúc, nhiều nhất một list là non-null. Nếu list1 đã cạn, list1 là None/null và biểu thức resolve về list2 (hoặc null nếu cả hai đã cạn). Toàn bộ list còn lại — vốn đã sắp xếp — kết nối trong O(1).

dummy.next là head thực sự. Bản thân dummy bị bỏ đi.

Đi từng bước qua ví dụ

Trace qua list1 = [1,2,4], list2 = [1,3,4] để thấy rõ từng bước di chuyển con trỏ:

Không có node nào được tạo mới. Mỗi node trong kết quả đã tồn tại trong list1 hoặc list2 — chúng ta chỉ nối lại các con trỏ next của chúng.

Tại sao dùng <= chứ không phải <

Phép so sánh dùng <=. Khi cả hai head bằng nhau, tôi lấy từ list1. Lựa chọn này tùy ý về mặt correctness — cả hai thứ tự đều cho ra list đã sắp xếp hợp lệ — nhưng <= làm cho merge stable: các node từ list1 xuất hiện trước các node cùng giá trị từ list2, giữ nguyên thứ tự tương đối. Stability quan trọng trong merge sort, và đây là subroutine mà merge sort gọi, nên thói quen này đáng xây dựng.

Giải pháp recursive

Cách tiếp cận recursive diễn đạt thuật toán theo cách bạn mô tả bằng lời: nếu head của list1 nhỏ hơn, list đã merge bắt đầu bằng head của list1, và phần đuôi là kết quả của việc merge phần còn lại của list1 với list2. Lặp lại cho đến khi một list rỗng, rồi list kia drop vào như phần đuôi.

class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        if not list1:
            return list2
        if not list2:
            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

public class Solution {
    public ListNode MergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
 
        if (list1.val <= list2.val) {
            list1.next = MergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = MergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

Mỗi lần gọi chọn một node và đệ quy vào bài toán thu nhỏ hơn. Base case xử lý trường hợp list rỗng — chính xác những gì dummy head xử lý cho phiên bản iterative. Để thấy call stack unwind như thế nào:

Độ sâu call đạt m+n trong trường hợp xấu nhất. Với list tối đa 50 node, đó là nhiều nhất 100 stack frame — ổn với bài này. Nhưng sẽ không ổn với Sort List (148), nơi bạn gọi hàm này trên các list có độ dài tùy ý như một phần của merge sort. Trong context đó, phiên bản iterative là bắt buộc.

Complexity

Cả hai đều chạm vào mỗi node đúng một lần. Sự khác biệt hoàn toàn nằm ở space: phiên bản iterative dùng số lượng pointer cố định, trong khi phiên bản recursive tích lũy stack frame tỷ lệ với tổng số node.

O(m + n) time là optimal — bạn phải xem qua mỗi node ít nhất một lần để biết nó thuộc vị trí nào trong output. Không có thuật toán nào thông minh hơn, vì bạn cần đọc toàn bộ output.

Các edge case

Cả hai giải pháp xử lý những trường hợp này mà không cần branching đặc biệt, điều đáng hiểu rõ:

Cả hai list rỗng. Vòng lặp không bao giờ chạy; current.next ở lại null. dummy.next là null. Với phiên bản recursive, base case đầu tiên return ngay lập tức.

Một list rỗng. Điều kiện while fail ngay. current.next được gán cho list non-null qua dòng gắn đuôi. Phiên bản recursive return list non-empty từ base case thứ hai.

Một list hoàn toàn nhỏ hơn list kia. Giả sử list1 = [1,2,3] và list2 = [4,5,6]. Vòng lặp drain list1 hoàn toàn, rồi current.next = list2 gắn toàn bộ list2 trong một bước. Không lãng phí iteration cho phần đuôi.

Tất cả giá trị bằng nhau. Điều kiện <= liên tục lấy từ list1, tạo ra interleaving stable: các node của list1 xuất hiện trước khi giá trị bằng nhau.

Giá trị âm. [-100, -50] merge với [-75, 0] chính xác như mong đợi — phép so sánh chỉ là integer comparison, và số nguyên âm so sánh đúng.

Phiên bản nào tôi thực sự dùng

Với LeetCode 21 độc lập, cả hai giải pháp đều pass. Với bất kỳ thứ gì downstream — merge sort, k-way merge, external merge — tôi sẽ dùng phiên bản iterative không cần suy nghĩ. Stack usage của phiên bản recursive bị giới hạn ở 100 frame ở đây, nhưng ngay khi bạn nhúng hàm này vào Sort List (148), merge sort bên ngoài đã dùng O(log n) stack frame rồi. Recursive merge cộng thêm O(n) frame nữa lên trên đó. Điều đó cộng dồn. Phiên bản iterative không có vấn đề này.

Còn về readability — phiên bản iterative là bốn thao tác pointer mỗi iteration. Phiên bản recursive trông elegant trên giấy nhưng bạn phải nghĩ qua quá trình unwind để thuyết phục bản thân rằng các pointer landing đúng. Tôi đã thấy người viết phiên bản recursive trong phỏng vấn rồi tự thuyết phục mình rằng nó không hoạt động — quá trình unwind không hiển nhiên lúc nhìn lần đầu.

Tôi sẽ dùng iterative. Dummy head là chi phí đầu vào, và đáng trả.

Pattern này xuất hiện ở đâu

Tín hiệu cho merge là "hai chuỗi đã sắp xếp, tạo ra một chuỗi đã sắp xếp." Khi thấy framing đó, pattern gần như tự động được kích hoạt. Nó xuất hiện bên trong các bài khác: merge sort gọi trực tiếp hàm này, external sort algorithms merge các sorted chunk, và một số bài interval có thể rút gọn thành merge sorted interval lists.

Mental model cơ bản là greedy selection từ các nguồn đã sắp xếp: vì cả hai input đã sắp xếp, phần tử nhỏ nhất còn lại toàn cục luôn ở head của một trong hai pointer. Greedy là optimal cục bộ, và vì input đã sắp xếp, optimal cục bộ cũng là optimal toàn cục. Đó là lý do tại sao một pass duy nhất là đủ.

Related problems

Merge Sorted Array (88) là logic merge tương tự trên array. Phiên bản thú vị là in-place, dùng ba pointer bắt đầu từ phía sau của các array để tránh shift phần tử.

Merge K Sorted Lists (23) mở rộng bài này cho k list. Gọi hàm này k - 1 lần hoạt động nhưng tốn O(nk) time — mỗi pass qua list đã merge là công việc lãng phí. Phiên bản hiệu quả dùng min-heap: luôn lấy head nhỏ nhất toàn cục trong O(log k) mỗi bước, tổng O(n log k). Logic merge bên trong y hệt những gì chúng ta viết ở đây.

Sort List (148) là merge sort trên linked list. Split tại midpoint với slow/fast pointer, đệ quy sort mỗi nửa, rồi gọi đúng hàm merge này để kết hợp lại. Phiên bản iterative ở đây là cái nên dùng — thêm recursive stack lên trên recursion của merge sort là không cần thiết.

Add Two Numbers (2) duyệt hai linked list node-by-node với carry, tương tự về pattern duyệt nhưng logic hoàn toàn khác. Đảm bảo sorted-order dẫn dắt merge pattern không áp dụng ở đó.