学习记录：js算法（三十四）：合并 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 elementscurrent.next = l1 || l2;return dummy.next;
}

讲解

1. 分解问题：将所有链表分为两组，递归地合并每一组中的链表。
2. 合并两组：当每一组中的链表已经被合并，再将这两组链表合并。
3. 基线条件：如果链表数组中只有一个链表，直接返回这个链表；如果没有链表，返回null。

以下是代码详细分析：

1. 主函数 mergeKLists

var mergeKLists = function(lists) {if (lists.length === 0) return null; // 如果链表数组为空，返回 nullif (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 合并两个已排序的链表。

2. 辅助函数 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 nodesconst compareNodes = (a, b) => a.val - b.val;// Initialize the heap with the first node of each listlists.forEach(list => {if (list) {heap.push(list);}});// Build the heapbuildMinHeap(heap, compareNodes);// Extract the smallest element and rebuild the heapwhile (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;
}

讲解

1. 初始化优先队列：创建一个最小堆（优先队列），并将每个链表的头节点（如果存在）插入堆中。堆中元素的比较基于链表节点的值。
2. 提取最小元素：从堆中弹出最小元素，将其添加到结果链表中。
3. 更新堆：如果弹出的节点有下一个节点，将其下一个节点插入堆中。
4. 重复步骤2和3：直到堆为空，即所有节点都被处理完毕。
5. 返回结果链表：返回结果链表的头节点。

总结

完全看不懂网上的写法。。。