当前位置： 面试刷题>> 合并 K 个升序链表(经典算法150题)
### 题目描述
合并 `k` 个升序链表，将 `k` 个升序链表合并为一个新的升序链表并返回。其中每个链表节点的定义如下（以 Python 为例，但其他语言类似）：
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
```
给定 `k` 个链表的头节点数组 `heads`，其中 `heads[i]` 是链表中第 `i` 个链表的头节点。
### 示例
#### 输入
```python
# 链表 1: 1->4->5
# 链表 2: 1->3->4
# 链表 3: 2->6
heads = [ListNode(1, ListNode(4, ListNode(5))), ListNode(1, ListNode(3, ListNode(4))), ListNode(2, ListNode(6))]
```
#### 输出
合并后的链表为：`1->1->2->3->4->4->5->6`
### 解题思路
有多种方法可以解决这个问题，包括使用优先队列（最小堆）来持续追踪所有链表当前的最小节点，或者使用分治法（将链表两两合并，直到合并为一个链表）。这里我们使用优先队列（最小堆）的方法，因为它在处理这类问题时通常更加高效。
### PHP 示例代码
PHP 不直接支持优先队列，但我们可以使用 SplPriorityQueue 来模拟。
```php
class ListNode {
public $val;
public $next;
function __construct($val = 0, $next = null) {
$this->val = $val;
$this->next = $next;
}
}
function mergeKLists($heads) {
$pq = new SplPriorityQueue();
$pq->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
// 初始化优先队列
foreach ($heads as $head) {
if ($head !== null) {
$pq->insert([$head->val, $head], $head->val);
}
}
$dummy = new ListNode(0);
$current = $dummy;
while (!$pq->isEmpty()) {
list($val, $node) = $pq->extract();
$current->next = $node;
$current = $current->next;
if ($node->next !== null) {
$pq->insert([$node->next->val, $node->next], $node->next->val);
}
}
return $dummy->next;
}
```
### Python 示例代码
Python 使用 `heapq` 模块来实现优先队列。
```python
import heapq
def mergeKLists(heads):
dummy = ListNode(0)
current = dummy
heap = []
# 初始化堆
for head in heads:
if head:
heapq.heappush(heap, (head.val, head))
while heap:
val, node = heapq.heappop(heap)
current.next = node
current = current.next
if node.next:
heapq.heappush(heap, (node.next.val, node.next))
return dummy.next
```
### JavaScript 示例代码
JavaScript 可以通过数组模拟优先队列，并使用 `Array.prototype.sort()` 来维护堆的性质。
```javascript
function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
function mergeKLists(heads) {
let dummy = new ListNode(0);
let current = dummy;
let heap = [];
// 初始化堆
for (let head of heads) {
if (head) {
heap.push({ val: head.val, node: head });
}
}
heap.sort((a, b) => a.val - b.val); // 初始排序
while (heap.length > 0) {
let { val, node } = heap.shift();
current.next = node;
current = current.next;
if (node.next) {
heap.push({ val: node.next.val, node: node.next });
heap.sort((a, b) => a.val - b.val); // 每次插入后重新排序
}
}
return dummy.next;
}
```
注意：JavaScript 示例中的堆实现不是最高效的，因为它在每次插入后都进行了全排序。在实际应用中，你可能需要使用更高效的堆实现，如二叉堆。不过，为了简化示例，这里使用了简单的数组和排序函数。