LeetCode:合并K个排序链表
2019-02-22 本文已影响57人
一萍之春
合并K个排序链表(困难)
题目叙述:
合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
解题思路:
我们先从其中的一个子问题开始看,那就是如何合并两个有序链表,我们可以先取起始一个值比较小的哪一个链表,作为我们的最后答案的链表的头,然后我们,用两个引用一个h1指向比较小的哪一个链表,h2指向比较大的那个链表进行,使h1.next.val与h2.val值进行比较,为什么要这样做呢?这样可以避免h2经过头插插入,使插入的情况变得更简单。两个指针联动跑起来,直到h1.next==null||h2==null,如果h1.next==null说明h2还有元素没有跑完但是现在比h1中所有都大,直接插入到尾部就好了。实现代码在最后实现代码中有这里就不单拿出来了。
然后我们的题目是k个,这样我们想归并排序的思维将我们所有的链表进行两两一组合并,然后直到合成只剩下最后一条放在lists[0]上就是我们最后的结果,可以看出两个链表合并时间复杂度为:O(n),归并的为O(logk),所以最终的时间复杂度为O(nlogk)。空间复杂度为O(1) PS:这是第一篇LeetCode中的难度为困难的,如有更好的解法请多多指教。
实现代码:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists==null||lists.length<1){
return null;
}
int len=lists.length;
if(len==1){
return lists[0];
}
int cnt=0;
while(len>1){
int mid=len/2;
for(int i=0;i<mid;i++){
lists[i]=mergeTwoLists(lists[2*i],lists[2*i+1]);
}
len=(len+1)/2;
if(len>mid){
lists[mid]=lists[2*mid];
}
}
return lists[0];
}
//合并两链表
public ListNode mergeTwoLists(ListNode list1,ListNode list2){
if(list1==null){
return list2;
}else if(list2==null){
return list1;
}
ListNode h1,h2;
if(list1.val<=list2.val){
h1=list1;
h2=list2;
}else{
h1=list2;
h2=list1;
}
ListNode res=h1;
while(h1.next!=null&&h2!=null){
if(h2.val<h1.next.val){
ListNode help=h2;
h2=h2.next;
help.next=h1.next;
h1.next=help;
}
h1=h1.next;
}
if(h1.next==null){
h1.next=h2;
}
return res;
}
}