23合并 K 个升序链表

我嘞个二维数组
有点小夸张了哈

这个题目我最开始看就回想两个有序链表的排序，但是如果这样排，那要排k次，每次排序还有相应时间复杂度，工程量之大，相当恐怖

那么这个时候我们就想起来去用堆
最小堆，非子叶节点小于子叶节点，可以导致根节点是最小的，那么我们只需要把所有数据全部插入最小堆，然后一一删去根节点即可

好几种解法放在下面
第一种用堆

class Solution {public ListNode mergeKLists(ListNode[] lists) {PriorityQueue<ListNode> pq=new PriorityQueue<>((a,b)->a.val-b.val);ListNode dummy=new ListNode(0);ListNode current=dummy;for(ListNode list:lists){if(list!=null){pq.offer(list);}}while(!pq.isEmpty()){ListNode node=pq.poll();current.next=node;current=current.next;if(node.next!=null){pq.offer(node.next);}}return dummy.next;}}

注意这个offer方法是把数组头结点放在最小堆，而不是把整个数组放进去
当然也可以直接放进去
poll方法是挑出最小的那个堆节点
如果想直接全部放进去就在第一个循环里面改成pq.add(list)即可

class Solution {public ListNode mergeKLists(ListNode[] lists) {if (lists == null || lists.length == 0) return null;return merge(lists, 0, lists.length - 1);}private ListNode merge(ListNode[] lists, int left, int right) {if (left == right) return lists[left];int mid = left + (right - left) / 2;ListNode l1 = merge(lists, left, mid);ListNode l2 = merge(lists, mid + 1, right);return mergeTwoLists(l1, l2);//主要是在这里面的l1和l2是二者都是有序链表，后面mergeTwoLists合并了}private ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);ListNode current = dummy;while (l1 != null && l2 != null) {if (l1.val <= l2.val) {current.next = l1;l1 = l1.next;} else {current.next = l2;l2 = l2.next;}current = current.next;}if (l1 != null) {current.next = l1;} else {current.next = l2;}return dummy.next;}
}

第二种这个直接用了最简单粗暴的，但是说实话还是有点难度的

class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public class Solution {public ListNode mergeKLists(ListNode[] lists) {if (lists == null || lists.length == 0) return null;int interval = 1;while (interval < lists.length) {for (int i = 0; i + interval < lists.length; i += interval * 2) {lists[i] = mergeTwoLists(lists[i], lists[i + interval]);}interval *= 2;}return lists[0];}private ListNode mergeTwoLists(ListNode l1, ListNode l2) {if (l1 == null) return l2;if (l2 == null) return l1;if (l1.val < l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;} else {l2.next = mergeTwoLists(l1, l2.next);return l2;}}
}