LeetCode Merge k Sorted Lists（合併 k 個有序鏈表）

一、題目描述

合併 k 個升序鏈表為一個升序鏈表並返回。

範例： 輸入：[[1,4,5],[1,3,4],[2,6]] → 輸出：1→1→2→3→4→4→5→6

二、解題思路：最小堆（優先隊列）

將所有鏈表的頭節點入堆，每次取出最小節點接入結果鏈表，並將該節點的下一節點入堆。利用堆維護當前最小值，時間複雜度 O(N log k)，N 為總節點數。

三、代碼實現（Python）

import heapq

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        heap = []
        for node in lists:
            if node:
                heapq.heappush(heap, (node.val, node))
        
        dummy = ListNode(-1)
        tail = dummy
        while heap:
            val, node = heapq.heappop(heap)
            tail.next = node
            tail = tail.next
            if node.next:
                heapq.heappush(heap, (node.next.val, node.next))
        return dummy.next

# 測試
if __name__ == "__main__":
    # 構建測試用例
    l1 = ListNode(1); l1.next = ListNode(4); l1.next.next = ListNode(5)
    l2 = ListNode(1); l2.next = ListNode(3); l2.next.next = ListNode(4)
    l3 = ListNode(2); l3.next = ListNode(6)
    res = Solution().mergeKLists([l1, l2, l3])
    while res:
        print(res.val, end=" ")
        res = res.next
    # 輸出: 1 1 2 3 4 4 5 6

四、複雜度分析

• 時間複雜度：O(N log k)
• 空間複雜度：O(k) 堆空間

Python 的 heapq 使代碼非常簡潔。也可用分治法（兩兩合併）達到相同複雜度。