LeetCode交流程序员二叉树之下

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;
    }
}
上一篇下一篇

猜你喜欢

热点阅读