基礎知識要求：

Java：方法、while循環、for循環、PriorityQueue類、if判斷

Python：?方法、while循環、for循環、heapq 模塊、if判斷

數據結構:隊列?

題目：?

給你一個鏈表數組，每個鏈表都已經按升序排列。

請你將所有鏈表合并到一個升序鏈表中，返回合并后的鏈表。

示例 1：

輸入：lists = [[1,4,5],[1,3,4],[2,6]]
輸出：[1,1,2,3,4,4,5,6]
解釋：鏈表數組如下：
[1->4->5,1->3->4,2->6
]
將它們合并到一個有序鏈表中得到。
1->1->2->3->4->4->5->6

示例 2：

輸入：lists = []
輸出：[]

示例 3：

輸入：lists = [[]]
輸出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i]?按?升序?排列
• lists[i].length?的總和不超過?10^4

思路解析：

對于合并多個已排序的列表或鏈表，一種常見的算法是使用最小堆（Min Heap）。在這個問題中，我們可以利用Python的heapq模塊來實現最小堆。

Python的heapq模塊不了解的，可以看一下我的這篇文章?Python 中的 heapq 模塊簡介

1. 初始化:
   • 創建一個虛擬頭節點dummy，它的作用是簡化鏈表的操作，因為我們可以直接操作dummy.next來構建結果鏈表，而不需要擔心頭節點為空的情況。
   • 創建一個指針p，指向dummy，它將用于遍歷并構建結果鏈表。
   • 創建一個空的最小堆heap，用于存儲待合并鏈表中的節點和它們的值。
2. 構建最小堆:
   • 遍歷所有輸入的鏈表lists。
   • 對于每個鏈表，如果鏈表不為空，將其頭節點的值和節點本身作為一個元組(val, node)加入最小堆中。這里，我們利用節點的值val作為堆排序的優先級。
3. 合并鏈表:
   • 當最小堆不為空時，執行以下步驟：
     • 從堆中彈出具有最小值的節點，即當前所有鏈表中的最小節點。
     • 將這個節點添加到結果鏈表中，即設置p.next = node，并移動指針p到下一個位置。
     • 如果彈出的節點有下一個節點（即node.next不為空），將這個節點的下一個節點和它的值作為一個新的元組(node.next.val, node.next)加入最小堆中。
4. 返回結果:
   • 返回虛擬頭節點的下一個節點dummy.next，這就是合并后的排序鏈表的頭節點。

Java代碼示例：

import java.util.PriorityQueue;  class ListNode {  int val;  ListNode next;  ListNode(int x) { val = x; }  
}  public class Solution {  public ListNode mergeKLists(ListNode[] lists) {  // 創建一個虛擬頭節點  ListNode dummy = new ListNode(0);  ListNode p = dummy;  // 創建一個優先隊列，按照節點的值排序  PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);  // 將所有鏈表的頭節點加入優先隊列  for (ListNode head : lists) {  if (head != null) {  pq.offer(head);  }  }  // 從優先隊列中取出最小節點，直到隊列為空  while (!pq.isEmpty()) {  ListNode node = pq.poll();  p.next = node;  p = p.next;  // 如果當前節點的下一個節點不為空，則加入優先隊列  if (node.next != null) {  pq.offer(node.next);  }  }  // 返回結果鏈表的頭節點（虛擬頭節點的下一個節點）  return dummy.next;  }  
}

Python代碼示例：

import heapq  class ListNode:  def __init__(self, val=0, next=None):  self.val = val  # 節點的值  self.next = next  # 指向下一個節點的指針  def mergeKLists(lists):  # 創建一個虛擬頭節點，這樣可以避免處理頭節點為空的情況  dummy = ListNode(0)    p = dummy  # p用于遍歷合并后的鏈表  # 創建一個最小堆，用于存儲(節點值, 節點)對，這樣我們可以根據節點值來排序  heap = []    # 遍歷所有輸入的鏈表，將非空鏈表的頭節點加入最小堆  for lst in lists:    if lst:  # 如果鏈表不為空  heapq.heappush(heap, (lst.val, lst))  # 將節點的值和節點作為一個元組加入堆  # 當堆不為空時，繼續合并鏈表  while heap:  # 彈出堆頂元素（即當前所有節點中的最小值節點）  val, node = heapq.heappop(heap)    # 將該節點連接到結果鏈表的末尾  p.next = node    p = p.next  # 移動指針到下一個位置  # 如果當前節點的下一個節點不為空，將其加入最小堆  if node.next:    heapq.heappush(heap, (node.next.val, node.next))    # 返回合并后鏈表的頭節點（虛擬頭節點的下一個節點）  return dummy.next  # 示例：創建三個鏈表并合并它們  
lists = [  ListNode(1, ListNode(4, ListNode(5))),  # 鏈表1: 1->4->5  ListNode(1, ListNode(3, ListNode(4))),  # 鏈表2: 1->3->4  ListNode(2, ListNode(6))  # 鏈表3: 2->6  
]  # 調用mergeKLists函數合并鏈表  
merged_list = mergeKLists(lists)  # 打印合并后的鏈表  
current = merged_list  
while current:  print(current.val, end='->')  # 打印當前節點的值，并在末尾添加"->"  current = current.next  # 移動到下一個節點  
print('None')  # 表示鏈表結束