我嘞个二维数组
有点小夸张了哈
这个题目我最开始看就回想两个有序链表的排序，但是如果这样排，那要排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;
}
}
}