[刷题]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轮即可合并完毕
这里盗一张官方题解的图片
6f70a6649d2192cf32af68500915d84b476aa34ec899f98766c038fc9cc54662-image.png
代码如下:

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);
    }

评论

暂无评论