[刷题]Leetcode23.合并K个排序链表
文章目录
题目描述:
合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
这道题目的链接在此
在看这道题之前 我们先来看看合并两个排序链表
思路很简单,两个链表都为空返回null,有一个为空时,返回另一个即可。当两个都不为空,用一个辅助结点作为新链表的头,取两个链表头部中值小的那个结点作为新链表的下一个结点,同时移动该链表和辅助结点。当其中一个链表为空了,就把另一个链表剩下的部分接到辅助结点后面。
代码如下:
public ListNode mergeTwo(ListNode l1, ListNode l2){
if(l1==null&&l2==null) return null;// 都为空则直接返回空
// 一个为空返回另一个
else if(l1==null) return l2;
else if (l2==null) return l1;
//两个都不为空
else {
ListNode head = new ListNode(-1);//新链表的辅助头
ListNode p = head;// 辅助结点
while (l1!=null||l2!=null){
// 其中一个为空,则直接接上剩下的结点
if(l2==null){
p.next = l1;
l1=null;
}
else if(l1==null){
p.next=l2;
l2=null;
}
// 取小的为下一个结点
else if(l1.val<=l2.val){
p.next = l1;
p = p.next;
l1=l1.next;
}
else {
p.next=l2;
p = p.next;
l2=l2.next;
}
}
return head.next;
}
( Hmm.. 不知道为什么空间只击败了15% .. 可能是辅助结点的缘由,你可以不用辅助结点,遍历前拿l1,l2小的那个作为头,我这里就不上两份代码了 )
好了 我们再来看23题,现在有k个链表,我们该怎么合并呢?
方法一.
顺着合并两个链表的思路,我们构造一个新链表,每次我们取出k个链表头里值最小的那个作为新链表的下一个结点,这样的话我们每一轮要遍历k个元素,因为每一轮只拿掉了一个元素,因此要遍历N轮,其中N为k个链表所有结点的个数。这样时间复杂度就是O(kN),因为只用一个辅助结点,因此空间复杂度为O(1).
再顺着这个思路下去,在每一轮比较的时候能不能更快些呢?其实我们可以采用堆排序,即优先队列,这样建堆用了O(k),每次比较只需要O(logk),
依然需要N轮比较,因此时间复杂度缩减为O(Nlogk),建堆的空间复杂度为O(k),[ 有人说建堆不需要额外空间,他们的理由是重复利用了结点,但是我个人认为,建堆需要的二叉树中的指针也需要占据空间吧,所以我认为空间复杂度是O(k) ]
代码如下:
public ListNode mergeKLists(ListNode[] lists) {
if (lists==null||lists.length<1) return null;
PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
@Override
public int compare(ListNode l1, ListNode l2) {
if(l1.val<l2.val) return -1;
else if(l1.val==l2.val) return 0;
else return 1;
}
});
ListNode head = new ListNode(-1);//辅助头
ListNode p = head; //辅助游标
// 建堆
for(ListNode l : lists) {
if(l!=null) queue.add(l);
}
while (!queue.isEmpty()){
// 取值最小的结点加入新链表
p.next = queue.poll();
// 该结点的后续结点加入优先队列
if(p.next.next!=null) queue.add(p.next.next);
// 游标移动
p = p.next;
}
return head.next;
}
方法二.不难想到,另一个比较直观的方法就是两两合并所有的链表,即第一个链表和第二个链表合并后,再和第三个链表合并,再和第四个链表合并... 这样每一轮需要O(n),n为两个链表的长度总和,共需要k轮,这样叠加起来共需要O(kN)的时间复杂度。
为了减少比较次数,我们改用分治法两两合并链表,比如[链表1,链表2],[链表3,链表4]..... 合并结束后,再合并[链表1_2,链表3_4].... 颇有归并排序的味道。这样每一轮所有两两合并结束,共需要比较N次,而分治法只需要logk轮即可合并完毕
这里盗一张官方题解的图片
代码如下:
public ListNode mergeKLists(ListNode[] lists) {
if (lists==null||lists.length<1) return null;
return merge(lists, 0,lists.length-1);
}
public ListNode merge(ListNode[] list, int left, int right){
if(left==right) return list[left];
int mid = (left+right)/2;
ListNode l1 = merge(list, left, mid);
ListNode l2 = merge(list,mid+1,right);
return mergeTwo(l1,l2);
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论