学习记录：js算法（三十四）：合并 K 个升序链表
文章目录
- 合并K个升序链表
- 我的思路
- 网上思路
- 总结
合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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 = [[]]
输出：[]
我的思路
递归+合并
也是网上思路，实在不会写了，照抄过来的。。。
网上思路
最小堆
我的思路
var mergeKLists = function(lists) {
if (lists.length === 0) return null;
if (lists.length === 1) return lists[0];
const mid = Math.floor(lists.length / 2);
const left = mergeKLists(lists.slice(0, mid));
const right = mergeKLists(lists.slice(mid));
return mergeTwoLists(left, right);
};
// Helper function to merge two sorted lists
function mergeTwoLists(l1, l2) {
const dummy = new ListNode(0);
let current = dummy;
while (l1 && l2) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
// Attach any remaining elements
current.next = l1 || l2;
return dummy.next;
}
讲解
- 分解问题：将所有链表分为两组，递归地合并每一组中的链表。
- 合并两组：当每一组中的链表已经被合并，再将这两组链表合并。
- 基线条件：如果链表数组中只有一个链表，直接返回这个链表；如果没有链表，返回null。
以下是代码详细分析：
- 主函数 mergeKLists
var mergeKLists = function(lists) { if (lists.length === 0) return null; // 如果链表数组为空，返回 null if (lists.length === 1) return lists[0]; // 如果只有一个链表，直接返回该链表 const mid = Math.floor(lists.length / 2); // 找到中间位置 const left = mergeKLists(lists.slice(0, mid)); // 递归合并左半部分 const right = mergeKLists(lists.slice(mid)); // 递归合并右半部分 return mergeTwoLists(left, right); // 合并左半部分和右半部分 };逻辑分析：
- 边界条件：
如果 lists 数组为空，返回 null。
如果 lists 数组中只有一个链表，直接返回该链表。- 分治法：
通过找到中间索引 mid 将链表数组分为两部分。
递归地对这两部分进行合并，最终调用 mergeTwoLists 合并两个已排序的链表。
- 辅助函数 mergeTwoLists
function mergeTwoLists(l1, l2) { const dummy = new ListNode(0); // 创建一个虚拟头节点 let current = dummy; // 用于跟踪合并链表的当前节点 while (l1 && l2) { // 当两个链表都不为空时 if (l1.val < l2.val) { // 比较当前节点的值 current.next = l1; // 将较小的节点连接到合并链表 l1 = l1.next; // 移动 l1 到下一个节点 } else { current.next = l2; // 将较小的节点连接到合并链表 l2 = l2.next; // 移动 l2 到下一个节点 } current = current.next; // 移动当前节点指针 } // 连接剩余的节点 current.next = l1 || l2; // 如果 l1 或 l2 还有剩余节点，连接到合并链表 return dummy.next; // 返回合并链表的头节点（跳过虚拟头节点） }逻辑分析：
- 虚拟头节点：
创建一个虚拟头节点 dummy 用于简化合并操作，避免处理空链表的特殊情况。- 合并过程
使用 while 循环遍历两个链表，比较当前节点的值，将较小的节点添加到合并链表中。
当其中一个链表遍历完后，直接将另一个链表的剩余部分连接到合并链表的末尾。
网上思路
var mergeKLists = function(lists) {
const dummy = new ListNode(0);
let current = dummy;
const heap = [];
// Helper function to compare nodes
const compareNodes = (a, b) => a.val - b.val;
// Initialize the heap with the first node of each list
lists.forEach(list => {
if (list) {
heap.push(list);
}
});
// Build the heap
buildMinHeap(heap, compareNodes);
// Extract the smallest element and rebuild the heap
while (heap.length > 0) {
const smallest = extractMin(heap, compareNodes);
current.next = smallest;
current = current.next;
if (smallest.next) {
heap.push(smallest.next);
buildMinHeap(heap, compareNodes);
}
}
return dummy.next;
};
// Helper functions for the heap operations
function buildMinHeap(array, compare) {
const n = array.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(array, n, i, compare);
}
}
function heapify(array, n, i, compare) {
let smallest = i;
const left = 2 * i + 1;
const right = 2 * i + 2;
if (left < n && compare(array[left], array[smallest]) < 0) {
smallest = left;
}
if (right < n && compare(array[right], array[smallest]) < 0) {
smallest = right;
}
if (smallest !== i) {
[array[i], array[smallest]] = [array[smallest], array[i]];
heapify(array, n, smallest, compare);
}
}
function extractMin(array, compare) {
const min = array[0];
array[0] = array[array.length - 1];
array.pop();
heapify(array, array.length, 0, compare);
return min;
}
讲解
- 初始化优先队列：创建一个最小堆（优先队列），并将每个链表的头节点（如果存在）插入堆中。堆中元素的比较基于链表节点的值。
- 提取最小元素：从堆中弹出最小元素，将其添加到结果链表中。
- 更新堆：如果弹出的节点有下一个节点，将其下一个节点插入堆中。
- 重复步骤2和3：直到堆为空，即所有节点都被处理完毕。
- 返回结果链表：返回结果链表的头节点。
总结
完全看不懂网上的写法。。。