【力扣】23. 合并 K 个升序链表 ＜链表指针、堆排序、分治＞

【力扣】23. 合并 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 = [[]]
输出：[]

提示：
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$

题解

方法一：暴力，先遍历取出来值到数组中排序，再生成新链表

import java.util.*;class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val;this.next = next; }
}class Solution {public ListNode mergeKLists(ListNode[] lists) {ListNode dummyNode = new ListNode(-1);ListNode prev = dummyNode;//先遍历取出来值到数组中排序List<Integer> nodes = new ArrayList();for(ListNode list: lists){while(list != null){nodes.add(list.val);list = list.next;}}Collections.sort(nodes);//生成新链表for(int x : nodes){prev.next = new ListNode(x);prev = prev.next;}return dummyNode.next;}
}

方法二：基础堆排序（使用优先队列 PriorityQueue）

思路：遍历数组每个值，建小顶堆，照着小顶堆依次取堆顶元素并移除，直到堆空

import java.util.*;class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val;this.next = next; }
}class Solution {public ListNode mergeKLists(ListNode[] lists) {//边界if (lists == null || lists.length == 0) {return null;}//创建一个堆（优先队列），并设置元素的排序方式PriorityQueue<ListNode> queue = new PriorityQueue(new Comparator<ListNode>() {@Overridepublic int compare(ListNode o1, ListNode o2) {return (o1.val - o2.val);}});//遍历链表数组，然后将每个链表的每个节点都放入堆中for(ListNode list: lists){while(list != null){queue.add(list);list = list.next;}}ListNode dummyNode = new ListNode(-1);ListNode prev = dummyNode;//从堆中不断取出元素，并将取出的元素串联起来while (!queue.isEmpty()) {prev.next = queue.poll();prev = prev.next;}prev.next = null;return dummyNode.next;}
}

方法三：基础堆排序（使用优先队列 PriorityQueue）

思路：只遍历每个数组第一个值（k 个），建小顶堆，照着小顶堆依次取堆顶元素并移除，移除的同时，如果这个值原来还有next 就补齐 k个到堆里，继续取堆顶移除。

因为：k 个链表中的最小值，一定来自 k 个递增链表中某一个的第一个值。将原先的 O(N) 的空间复杂度优化到 O(k)

import java.util.*;class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val;this.next = next; }
}class Solution {public ListNode mergeKLists(ListNode[] lists) {//边界if (lists == null || lists.length == 0) {return null;}//创建一个小根堆，并定义好排序函数PriorityQueue<ListNode> queue = new PriorityQueue(new Comparator<ListNode>() {@Overridepublic int compare(ListNode o1, ListNode o2) {return (o1.val - o2.val);}});//这里不再是一股脑全部放到堆中,而是只把 k 个链表的第一个节点放入到堆中for (ListNode list : lists) {ListNode eachHead = list;if (eachHead != null) {queue.add(eachHead);}}ListNode dummyNode = new ListNode(-1);ListNode prev = dummyNode;//之后不断从堆中取出节点，如果这个节点所在的链表还有下一个节点，就将下个节点也放入堆中while (queue.size() > 0) {ListNode node = queue.poll();prev.next = node;prev = prev.next;if (node.next != null) {queue.add(node.next);}}prev.next = null;return dummyNode.next;}
}

方法四：递归

合并两个链表的思路来合并 k 个链表

class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val;this.next = next; }
}class Solution {public ListNode mergeKLists(ListNode[] lists) {// 边界if (lists == null || lists.length == 0) {return null;}// 将 lists[0] 作为最终合并的链表，然后将 list[0] 和 lists[1] 合并成 lists[0-1]// 再将 lists[0-1] 和 lists[2] 合并，如此反复最终 lists[0] 就是最终结果ListNode res = lists[0];for (int i = 1; i < lists.length; i++) {res = merge(res, lists[i]);}return res;}// 合并两个有序链表,递归版本private ListNode merge(ListNode l1, ListNode l2) {//递归的结束条件，如果 l1 和 l2 中有一个为空就返回if (l1 == null || l2 == null) {return (l1 == null) ? l2 : l1;}//如果 l1 的值 <=l2 的值，就继续递归，比较 l1.next 的值和 l2 的值//l1.next 和 l2 比较完后，会产生一个更小的节点 x，将 x 加到当前 l1 的后面if (l1.val <= l2.val) {l1.next = merge(l1.next, l2);return l1;}//如果 l1 的值 >l2 的值，就继续递归，比较 l1 的值和 l2.next 的值else {l2.next = merge(l1, l2.next);return l2;}}
}

方法五：分治

  一开始数组的规模是 k，找到中间点，一分为二，然后再拆分，直到不能再拆分 (规模为1时) 时便返回。之后开始合并，合并的代码借用了合并两个排序链表的代码。
  当两个规模最小的链表合并完后，其规模就变大了，然后不断重复这个合并过程，直到最终得到一个有序的链表。
  分治就是不断缩小其规模，再不断合并扩大的过程

class Solution {public ListNode mergeKLists(ListNode[] lists) {// 边界if (lists == null || lists.length == 0) {return null;}//分治return helper(lists, 0, lists.length - 1);}//通过合并两个链表，不断增大其规模，整体看就是不断缩小-最后不断扩大的过程private ListNode helper(ListNode[] lists, int begin, int end) {if (begin == end) {return lists[begin];}//通过 mid 将数组一分为二，并不断缩小规模，当规模为 1 时返回并开始合并int mid = begin + (end - begin) / 2;ListNode left = helper(lists, begin, mid);ListNode right = helper(lists, mid + 1, end);return merge(left, right);}// 合并两个有序链表,递归版本private ListNode merge(ListNode l1, ListNode l2) {//递归的结束条件，如果 l1 和 l2 中有一个为空就返回if (l1 == null || l2 == null) {return (l1 == null) ? l2 : l1;}//如果 l1 的值 <=l2 的值，就继续递归，比较 l1.next 的值和 l2 的值//l1.next 和 l2 比较完后，会产生一个更小的节点 x，将 x 加到当前 l1 的后面if (l1.val <= l2.val) {l1.next = merge(l1.next, l2);return l1;}//如果 l1 的值 >l2 的值，就继续递归，比较 l1 的值和 l2.next 的值else {l2.next = merge(l1, l2.next);return l2;}}
}