23. Merge k Sorted Lists
給定一個包含 k 個鏈表的數組 lists，每個鏈表都按升序排序。
將所有鏈表合併成一個排序的鏈表，並返回它。
範例 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
Python
from typing import List, Optional
import heapq
# Definition for singly-linked list.
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]:
# Define a min-heap
min_heap = []
# Initialize the heap with the head nodes of each list
for i, node in enumerate(lists):
if node:
heapq.heappush(min_heap, (node.val, i, node))
# Create a dummy node to help with merging
dummy = ListNode()
current = dummy
# Merge the lists
while min_heap:
# Get the smallest element from the heap
val, i, node = heapq.heappop(min_heap)
current.next = ListNode(val)
current = current.next
node = node.next
# If there is a next node, add it to the heap
if node:
heapq.heappush(min_heap, (node.val, i, node))
# Return the merged list, which starts at dummy.next
return dummy.next
19.70MB, 79ms
C++
#include <vector>
#include <queue>
using namespace std;
// Assume ListNode is already defined elsewhere
// struct ListNode {
// int val;
// ListNode* next;
// ListNode() : val(0), next(nullptr) {}
// ListNode(int x) : val(x), next(nullptr) {}
// ListNode(int x, ListNode* next) : val(x), next(next) {}
// };
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
// Define a lambda function for the comparison in the priority queue
(min-heap)
auto comp = [](ListNode* a, ListNode* b) {
return a->val > b->val;
};
// Define a priority queue (min-heap)
priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> minHeap(comp);
// Initialize the heap with the head nodes of each list
for (auto node : lists) {
if (node) {
minHeap.push(node);
}
}
// Create a dummy node to help with merging
ListNode dummy;
ListNode* current = &dummy;
// Merge the lists
while (!minHeap.empty()) {
// Get the smallest element from the heap
ListNode* node = minHeap.top();
minHeap.pop();
current->next = node;
current = current->next;
// If there is a next node, add it to the heap
if (node->next) {
minHeap.push(node->next);
}
}
// Return the merged list, which starts at dummy.next
return dummy.next;
}
};
16.84MB, 16ms
Javascript
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val);
* this.next = (next===undefined ? null : next);
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
// Define a helper function to manage the priority queue
class MinHeap {
constructor() {
this.heap = [];
}
insert(node) {
this.heap.push(node);
this.bubbleUp(this.heap.length - 1);
}
bubbleUp(index) {
while (index > 0) {
let parentIndex = Math.floor((index - 1) / 2);
if (this.heap[index].val >= this.heap[parentIndex].val) break;
[this.heap[index], this.heap[parentIndex]] =
[this.heap[parentIndex], this.heap[index]];
index = parentIndex;
}
}
extractMin() {
if (this.heap.length === 1) return this.heap.pop();
let min = this.heap[0];
this.heap[0] = this.heap.pop();
this.bubbleDown(0);
return min;
}
bubbleDown(index) {
while (true) {
let leftIndex = 2 * index + 1;
let rightIndex = 2 * index + 2;
let smallest = index;
if (leftIndex < this.heap.length && this.heap[leftIndex].val <
this.heap[smallest].val) {
smallest = leftIndex;
}
if (rightIndex < this.heap.length && this.heap[rightIndex].val <
this.heap[smallest].val) {
smallest = rightIndex;
}
if (smallest === index) break;
[this.heap[index], this.heap[smallest]] = [this.heap[smallest],
this.heap[index]];
index = smallest;
}
}
isEmpty() {
return this.heap.length === 0;
}
}
// Initialize the min-heap
const minHeap = new MinHeap();
// Add the head nodes of each list to the heap
for (let node of lists) {
if (node !== null) {
minHeap.insert(node);
}
}
// Create a dummy node to help with merging
let dummy = new ListNode();
let current = dummy;
// Merge the lists
while (!minHeap.isEmpty()) {
let node = minHeap.extractMin();
current.next = node;
current = current.next;
// If there is a next node, add it to the heap
if (node.next !== null) {
minHeap.insert(node.next);
}
}
// Return the merged list, which starts at dummy.next
return dummy.next;
};
61.73MB, 122ms
