23. Merge k Sorted Lists

Hard

Description

給定一個由 k 個已排序鏈結串列組成的陣列，將所有串列合併成一個排序的鏈結串列並回傳。

Example:

Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6]

Intuition#

核心思路：每次從 k 個串列的頭部選最小值，用 Min Heap 將選擇從 O(k) 降到 O(log k)。

暴力法：每次遍歷 k 個頭節點找最小值，共 N 個節點，時間 O(Nk)
Min Heap：維護 k 個頭節點的最小堆，每次取最小值只要 O(log k)
Divide and Conquer：兩兩合併，每輪串列數減半，共 log k 輪

Approaches#

1: Divide and Conquer#

概念: 類似 Merge Sort 的分治法，每輪將 k 個串列兩兩配對合併，共需 log k 輪
時間複雜度: O(N log k) - N 為總節點數，log k 輪合併
空間複雜度: O(log k) - 遞迴深度

class Solution {
    fun mergeKLists(lists: Array<ListNode?>): ListNode? {
        if (lists.isEmpty()) return null
        return merge(lists, 0, lists.size - 1)
    }

    private fun merge(lists: Array<ListNode?>, left: Int, right: Int): ListNode? {
        if (left == right) return lists[left]

        val mid = left + (right - left) / 2
        val l1 = merge(lists, left, mid)
        val l2 = merge(lists, mid + 1, right)
        return mergeTwoLists(l1, l2)
    }

    private fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
        val dummy = ListNode(0)
        var tail = dummy
        var p1 = l1
        var p2 = l2

        while (p1 != null && p2 != null) {
            if (p1.`val` <= p2.`val`) {
                tail.next = p1
                p1 = p1.next
            } else {
                tail.next = p2
                p2 = p2.next
            }
            tail = tail.next!!
        }
        tail.next = p1 ?: p2

        return dummy.next
    }
}

⭐2: Min Heap (Priority Queue)#

概念: 將 k 個串列的頭節點放入最小堆，每次取出最小節點接到結果串列，並將該節點的下一個節點加入堆中
時間複雜度: O(N log k) - 每個節點入堆出堆各一次，每次 O(log k)
空間複雜度: O(k) - 堆中最多 k 個節點

class Solution {
    fun mergeKLists(lists: Array<ListNode?>): ListNode? {
        val pq = PriorityQueue<ListNode>(compareBy { it.`val` })

        for (list in lists) {
            if (list != null) pq.offer(list)
        }

        val dummy = ListNode(0)
        var tail = dummy

        while (pq.isNotEmpty()) {
            val node = pq.poll()
            tail.next = node
            tail = node
            if (node.next != null) {
                pq.offer(node.next)
            }
        }

        return dummy.next
    }
}

注意空串列的處理：lists 中可能包含 null 元素，加入 PriorityQueue 前要檢查。

🔑 Takeaways#

Pattern: 「合併 k 個有序序列」是經典問題，Min Heap 和 Divide and Conquer 都是標準解法
關鍵技巧: PriorityQueue 搭配 compareBy 在 Kotlin 中非常簡潔；Divide and Conquer 可複用 mergeTwoLists 子程序