Merge K Sorted Lists: tại sao O(k²N) vỡ trận và hai chiến lược O(N log k) sửa nó thế nào

Nhìn sơ qua, bài này trông như một sự mở rộng bình thường: bạn đã biết cách gộp hai danh sách liên kết đã sắp xếp, nên k danh sách chắc chỉ là làm đi làm lại thêm vài lần nữa. Trực giác đó hoàn toàn đúng — nhưng "vài lần nữa" chính là nơi chi phí ẩn náu. Nếu bạn lần lượt gộp danh sách 1 vào kết quả, rồi danh sách 2, rồi danh sách 3, danh sách kết quả đang tăng dần sẽ bị duyệt lại mỗi lần. Đến khi xong, bạn đã thực hiện O(k²N) phép so sánh. Với k lên đến 10^4 và tổng số node N lên đến 10^4, đó là hàng trăm triệu phép tính trong trường hợp xấu nhất. Các constraints đang bảo bạn phải nghĩ kỹ hơn.

Đề bài

Cho một mảng gồm k linked list, mỗi danh sách đã được sắp xếp theo thứ tự tăng dần. Gộp tất cả chúng thành một linked list đã sắp xếp duy nhất và trả về nó. Đề gốc: LeetCode 23.

Ràng buộc:
- k == lists.length
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- -10^4 <= lists[i][j] <= 10^4
- lists[i] đã được sắp xếp theo thứ tự tăng dần.
- Tổng của lists[i].length sẽ không vượt quá 10^4.

Constraints nói gì

k == lists.length, 0 <= k <= 10^4, 0 <= lists[i].length <= 500, tổng node <= 10^4, giá trị trong [-10^4, 10^4].

Ba điểm nổi bật. Thứ nhất, k có thể lên đến mười nghìn. Bất kỳ thuật toán nào thực hiện O(k) công việc mỗi node là O(kN) tổng thể, với cả k lẫn N ở mức 10^4 là 10^8 phép tính — chậm. Đây là ngưỡng loại bỏ cách tiếp cận linear scan ngây thơ trong các tình huống thực tế.

Thứ hai, tổng số node N cũng bị giới hạn ở 10^4. Vậy N và k có cùng bậc độ lớn. Điều đó khiến O(N log k) — khoảng 10^4 * 14 — rất thoải mái.

Thứ ba, dải giá trị [-10^4, 10^4] có dấu và bao gồm số âm. Bạn không thể dùng 0 làm sentinel và không thể bỏ qua giá trị âm khi xây dựng min heap. Logic so sánh phải dựa trên giá trị thực.

Tính đã sắp xếp trong từng danh sách là món quà cấu trúc mà bài toán cho bạn. Nó có nghĩa là bạn không bao giờ cần nhìn vào bên trong một danh sách sâu hơn head hiện tại — ứng viên minimum từ mỗi danh sách luôn nằm ở đầu. Cả hai approach hiệu quả đều khai thác điều này một cách trực tiếp.

Approach 1: Brute force — linear scan tìm minimum mỗi bước

Cách đọc ngây thơ nhất của "tìm minimum rồi advance": ở mỗi bước, duyệt qua tất cả k head của danh sách và tìm cái nhỏ nhất, gắn vào kết quả, advance danh sách đó. Lặp lại cho đến khi tất cả danh sách cạn.

from typing import List, Optional
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
 
        dummy = ListNode(0)
        current = dummy
 
        while True:
            min_val = float('inf')
            min_idx = -1
 
            for i in range(len(lists)):
                if lists[i] is not None and lists[i].val < min_val:
                    min_val = lists[i].val
                    min_idx = i
 
            if min_idx == -1:
                break
 
            current.next = lists[min_idx]
            current = current.next
            lists[min_idx] = lists[min_idx].next
 
        return dummy.next

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}
 
public class Solution {
    public ListNode MergeKLists(ListNode[] lists) {
        if (lists == null || lists.Length == 0) return null;
 
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
 
        while (true) {
            int minVal = int.MaxValue;
            int minIdx = -1;
 
            for (int i = 0; i < lists.Length; i++) {
                if (lists[i] != null && lists[i].val < minVal) {
                    minVal = lists[i].val;
                    minIdx = i;
                }
            }
 
            if (minIdx == -1) break;
 
            current.next = lists[minIdx];
            current = current.next;
            lists[minIdx] = lists[minIdx].next;
        }
 
        return dummy.next;
    }
}

Mỗi node tốn một lần duyệt qua k con trỏ danh sách để tìm minimum. N node tổng cộng nghĩa là N lượt duyệt, cho O(k * N) time. Space là O(1) — không có cấu trúc phụ trợ, chỉ thao tác con trỏ.

Điểm yếu rất rõ: mỗi lần extract node yêu cầu duyệt toàn bộ k danh sách. Khi k lớn, hầu hết trong số k phép so sánh đó bị lãng phí vì bạn đang xem lại những danh sách mà head của chúng lớn hơn minimum hiện tại. Bạn đang bỏ phí tính sắp xếp mà bài toán cho bạn miễn phí.

Approach 2: Min heap — extraction O(log k)

Cách sửa cấu trúc là trực tiếp: thay thế linear scan O(k) bằng một min heap giữ đúng một entry cho mỗi danh sách đang active. Extract minimum giờ chỉ tốn O(log k), và sau mỗi lần extract bạn push node tiếp theo từ cùng danh sách đó vào. Heap size không bao giờ vượt quá k.

import heapq
from typing import List, Optional
 
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
 
        heap = []
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))
 
        dummy = ListNode(0)
        current = dummy
 
        while heap:
            val, list_idx, node = heapq.heappop(heap)
            current.next = node
            current = current.next
            if node.next:
                heapq.heappush(heap, (node.next.val, list_idx, node.next))
 
        return dummy.next

Tuple (node.val, list_idx, node) mang theo list index như một tiebreaker. Python's heap so sánh tuple theo từng phần tử, nên khi hai node có cùng giá trị, phép so sánh rơi xuống list_idx (một int) thay vì cố so sánh các đối tượng ListNode — điều đó sẽ raise TypeError. Đây không phải tối ưu nhỏ; thiếu nó, code crash ngay khi gặp giá trị trùng nhau.

using System.Collections.Generic;
 
public class Solution {
    public ListNode MergeKLists(ListNode[] lists) {
        if (lists == null || lists.Length == 0) return null;
 
        // PriorityQueue<TElement, TPriority> có từ .NET 6+
        var pq = new PriorityQueue<(int listIdx, ListNode node), int>();
 
        for (int i = 0; i < lists.Length; i++) {
            if (lists[i] != null) {
                pq.Enqueue((i, lists[i]), lists[i].val);
            }
        }
 
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
 
        while (pq.Count > 0) {
            var (listIdx, node) = pq.Dequeue();
            current.next = node;
            current = current.next;
            if (node.next != null) {
                pq.Enqueue((listIdx, node.next), node.next.val);
            }
        }
 
        return dummy.next;
    }
}

PriorityQueue của C# (thêm vào từ .NET 6) nhận priority là argument riêng, nên không có vấn đề tiebreaker — priority chỉ là giá trị integer, còn element là cặp (listIdx, node). Sạch hơn cách workaround của Python.

Time: O(N log k). Mỗi trong số N node được push một lần và pop một lần, và mỗi thao tác trên heap tốn O(log k). Space: O(k) cho heap, giữ tối đa k entry tại bất kỳ thời điểm nào.

Trace từng bước: lists = [[1,4,5],[1,3,4],[2,6]]

Hãy đi qua ví dụ cụ thể từ bài toán.

Heap ban đầu (sau khi seed với head của từng danh sách):
  heap = [(1, idx=0, node->1->4->5), (1, idx=1, node->1->3->4), (2, idx=2, node->2->6)]
  result: dummy ->

Bước 1: pop (1, 0, node->1)
  gắn node(1) vào result
  push node tiếp theo(4) từ list 0 -> heap = [(1,1,->1->3->4), (2,2,->2->6), (4,0,->4->5)]
  result: dummy -> 1

Bước 2: pop (1, 1, node->1)
  gắn node(1) vào result
  push node tiếp theo(3) từ list 1 -> heap = [(2,2,->2->6), (3,1,->3->4), (4,0,->4->5)]
  result: dummy -> 1 -> 1

Bước 3: pop (2, 2, node->2)
  gắn node(2) vào result
  push node tiếp theo(6) từ list 2 -> heap = [(3,1,->3->4), (4,0,->4->5), (6,2,->6)]
  result: dummy -> 1 -> 1 -> 2

Bước 4: pop (3, 1, node->3)
  gắn node(3) vào result
  push node tiếp theo(4) từ list 1 -> heap = [(4,0,->4->5), (4,1,->4), (6,2,->6)]
  result: dummy -> 1 -> 1 -> 2 -> 3

Bước 5: pop (4, 0, node->4)
  gắn node(4) vào result
  push node tiếp theo(5) từ list 0 -> heap = [(4,1,->4), (5,0,->5), (6,2,->6)]
  result: dummy -> 1 -> 1 -> 2 -> 3 -> 4

Bước 6: pop (4, 1, node->4)
  gắn node(4), list 1 cạn (node.next == null)
  heap = [(5,0,->5), (6,2,->6)]
  result: dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> 4

Bước 7: pop (5, 0, node->5)
  gắn node(5), list 0 cạn
  heap = [(6,2,->6)]
  result: dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5

Bước 8: pop (6, 2, node->6)
  gắn node(6), list 2 cạn
  heap = []
  result: dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

Heap rỗng. Trả về dummy.next.

Heap không bao giờ tăng quá 3 entry (k = 3). Mỗi lần extraction đảm bảo lấy được global minimum trong số tất cả các head còn lại.

Approach 3: Divide and conquer — merge sort áp dụng cho danh sách

Thay vì xử lý từng node một, bạn có thể tái cấu trúc toàn bộ bài toán. Ghép đôi k danh sách và gộp từng cặp. Bạn có k/2 danh sách. Ghép đôi lại. Sau log k vòng, bạn có một danh sách đã gộp.

from typing import List, Optional
 
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        return self._divide(lists, 0, len(lists) - 1)
 
    def _divide(self, lists, start, end):
        if start == end:
            return lists[start]
        if start > end:
            return None
        mid = (start + end) // 2
        left = self._divide(lists, start, mid)
        right = self._divide(lists, mid + 1, end)
        return self._merge_two(left, right)
 
    def _merge_two(self, l1, l2):
        dummy = ListNode(0)
        cur = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 or l2
        return dummy.next

public class Solution {
    public ListNode MergeKLists(ListNode[] lists) {
        if (lists == null || lists.Length == 0) return null;
        return Divide(lists, 0, lists.Length - 1);
    }
 
    private ListNode Divide(ListNode[] lists, int start, int end) {
        if (start == end) return lists[start];
        if (start > end) return null;
        int mid = (start + end) / 2;
        ListNode left = Divide(lists, start, mid);
        ListNode right = Divide(lists, mid + 1, end);
        return MergeTwo(left, right);
    }
 
    private ListNode MergeTwo(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 ?? l2;
        return dummy.next;
    }
}

Recursion tree trông như thế này với k = 4:

Mỗi level của cây xử lý tất cả N node đúng một lần. Có log k level. Tổng công việc: O(N log k). Stack depth là O(log k) cho các recursion frame.

Time: O(N log k), giống heap. Space: O(log k) cho call stack — tốt hơn rõ ràng so với O(k) của heap khi k lớn.

Các edge case cần chú ý

Input rỗng (lists = []): Guard if not lists / if lists.Length == 0 kích hoạt và trả về null. Không có gì để gộp.

Mảng chứa danh sách rỗng (lists = [[]] hoặc lists = [null, null]): Approach heap không seed entry nào — mọi head đều là null, nên không có gì được push. Vòng while không bao giờ chạy. Trả về dummy.next = null. Approach divide and conquer trả về lists[0] là null. Cả hai đúng.

Chỉ một danh sách (k = 1): Heap seed một entry, lập tức pop nó, push phần còn lại của danh sách từng node một. Trả về danh sách không thay đổi. Divide and conquer đụng start == end ngay lập tức và trả về lists[0]. Kết quả một dòng, không merge thực sự.

Tất cả node có cùng giá trị: Tiebreaker list_idx trong Python ngăn TypeError. PriorityQueue của C# xử lý tự nhiên vì priority là int. Thứ tự giữa các node cùng giá trị từ các danh sách khác nhau ổn định theo list index — nhất quán nhưng bài toán không yêu cầu stability.

Giá trị âm: Dải giá trị bao gồm -10^4. Phép so sánh trong heap dựa trên giá trị integer thực, kể cả số âm. Không cần xử lý đặc biệt. Thứ tự sắp xếp tăng dần trong từng danh sách vẫn đúng bất kể dấu.

Danh sách có độ dài rất khác nhau: Một danh sách có thể có 500 node, cái khác chỉ có 1. Heap xử lý điều này trong suốt — danh sách dài tiếp tục feed node vào từng cái một khi chúng được extract, danh sách ngắn đóng góp node duy nhất của mình rồi im lặng. Divide and conquer xử lý tốt không kém vì việc gộp hai danh sách có độ dài khác nhau chính là base case.

Bảng so sánh

Cả heap lẫn divide-and-conquer đều đạt O(N log k). Sự khác biệt nằm ở space và cách tổ chức công việc. Heap xử lý node từng cái một qua global minimum extraction. Divide and conquer xử lý chúng theo lô bằng cách giảm kích thước bài toán theo cấp số logarit.

Cái nào tôi sẽ dùng, và tại sao

Trong phỏng vấn, tôi chọn min heap. Logic trong suốt, code ngắn, và trick tiebreaker trong Python là tín hiệu thực sự rằng bạn đã nghĩ qua chi tiết implementation chứ không chỉ mô tả thuật toán. Khi interviewer hỏi bạn xử lý giá trị trùng thế nào, bạn có thể chỉ thẳng vào list_idx trong tuple. Cuộc trò chuyện đó dễ dàng.

Với code production nơi k có thể lớn và stack depth quan trọng — ví dụ, một database engine gộp các sorted run từ các worker song song — tôi sẽ ưu tiên divide and conquer. Stack depth O(log k) rất khó đạt đến giới hạn, và cấu trúc ánh xạ tự nhiên sang thực thi song song: bạn có thể chạy các nhánh độc lập trên các core riêng biệt. Heap không thể song song hóa gọn như vậy vì mỗi lần extraction phải đi qua heap state chung.

Trong thực tế, các hằng số ưu tiên heap một chút với k nhỏ (overhead quản lý heap thấp hơn overhead recursive call). Khi k đạt đến hàng trăm, space footprint thấp hơn của divide-and-conquer bắt đầu quan trọng. Chọn dựa trên constraints thực tế của bạn.

Pattern cơ bản và nơi nó xuất hiện

Tên của pattern này là k-way merge. Pattern xuất hiện bất cứ đâu bạn có k sequence đã sắp xếp và cần tạo ra một sequence đã sắp xếp hiệu quả. Heap là implementation chuẩn: seed với một phần tử mỗi sequence, luôn extract minimum, luôn bổ sung từ cùng sequence đó. Divide-and-conquer là biến thể merge-sort: giảm k sequence xuống còn 1 bằng cách giảm đôi số lượng mỗi level.

Cả hai pattern chuyển giao trực tiếp ngoài linked list. Các sequence có thể là mảng, iterator từ file trên đĩa, hoặc stream từ network socket. Logic merge không thay đổi; chỉ cấu trúc dữ liệu thay đổi.

Vị trí trong series linked-list

Đây là bài merge khó nhất trong series linked-list. Các bài trước đặt nền tảng: Merge Two Sorted Lists (21) là primitive mà mọi approach ở đây đều dùng làm building block — nếu bạn chưa nắm chắc bài two-list merge đó, hãy bắt đầu từ đó. Reverse Linked List (206) và Reorder List (143) mỗi bài thêm một bước thao tác con trỏ lên trên một traversal; chúng đơn giản hơn bài này. Sort List (148) là bước tiếp theo tự nhiên: áp dụng divide-and-conquer merge sort để sắp xếp một danh sách liên kết chưa sắp xếp, về cơ bản là bài này chạy ngược — xây dựng các sorted run trước, rồi gộp chúng.

Bốn bài đáng kết nối:

Find K Pairs with Smallest Sums (373) dùng min heap để extract k cặp nhỏ nhất từ hai mảng — cùng k-way extraction dựa trên heap, áp dụng cho một sequence ảo của các cặp ứng viên thay vì node danh sách thực tế.

Kth Smallest Element in a Sorted Matrix (378) coi mỗi hàng là một danh sách đã sắp xếp và hỏi phần tử nhỏ thứ k tổng thể. Approach heap từ bài này áp dụng trực tiếp: seed heap với phần tử đầu của mỗi hàng.

Smallest Range Covering Elements from K Lists (632) mở rộng bài này bằng cách hỏi không phải danh sách đã gộp mà là cửa sổ hẹp nhất chứa ít nhất một phần tử từ mỗi danh sách. Cùng cấu trúc heap, câu hỏi khác được đặt ra tại mỗi bước extraction.

Merge Sorted Array (88) là phiên bản mảng của two-list merge: constraints đơn giản hơn nhưng cùng logic so sánh. Đáng giải nếu bạn muốn thấy cách trick dummy-node biến mất khi bạn có không gian output được cấp phát sẵn.