X

LEETCODE 23. Merge k Sorted Lists 解题思路分析

题目大意:

合并K个排序链表

合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=23

解题思路分析:

听说最近有公司考到了这一题,因此决定二刷本题来压压惊。其实本题是LEETCODE 21. Merge Two Sorted Lists 解题思路分析的续集。

解法一:

前一题是合并2个链表,而本题是合并多个,核心思路没有太大差别,我们也需要两两合并,最终将多个合并成一个即可。最简单的方式即是先将前两个合并,然后再与第三个合并,再与第四个,第五个。。。直到所有合并结束。

实现代码:

public ListNode mergeKLists(ListNode[] lists) {
    // 如果数组为空,返回空
    if(lists.length==0) return null;
    // 首个链表
    ListNode node=lists[0];
    for(int i=1;i<lists.length;i++){
        // 将当前链表与首个链表合并,并将合并后链表赋值给node
        node=merge(node, lists[i]);
    }
    return node;
}
// 合并2个链表
ListNode merge(ListNode l1, ListNode l2){
    if(l1==null) return l2;
    if(l2==null) return l1;
    ListNode node;
    if(l1.val<=l2.val){
        node=new ListNode(l1.val);
        node.next = merge(l1.next, l2);
    }else{
        node=new ListNode(l2.val);
        node.next = merge(l1, l2.next);
    }
    return node;
}

本解法执行时间为341ms。

Runtime: 341 ms, faster than 5.06% of Java online submissions for Merge k Sorted Lists.

Memory Usage: 43.2 MB, less than 27.33% of Java online submissions for Merge k Sorted Lists.


解法二:

解法一的代码提交后发现,执行效率并不是很高。原因在于n个链表我们需要合并n次。进而想到使用分治法, 我们两两合并,这样经过第一次合并后,链表个数减半,我们一直重复这个过程,直到最后剩余一个链表为止。 这种思路实际上也是做了n次合并,但为什么会比第一种方式更好呢?

本题优化的关键在于每次合并时遍历的节点数量。解法一中,假设有k个链表,每个链表结点数一样都为 n,第一次合并时,要遍历 2n 个结点,往后则要分别遍历 3n, 4n, … , kn 个结点。可以看到,每次进行合并时都要将之前所有的链表遍历一次,因此这个方法的时间复杂度较高 。

而解法二,第一次合并时,要进行k/2次合并,每次合并要遍历 2n 个结点;第二次合并时,要进行4/k次合并,每次合并要遍历 4n 个结点;最后一次合并过程需要遍历 kn 次结点。这样效率会大幅改善,我们更直接的看下两种解法的复杂度差别,比如我们有8个链表,每个链表有10个节点,那么:

// 解法一每次合并需要遍历的节点数量:
20+30+40+50+60+70+80=350
// 解法二每次合并需要遍历的节点数量:
20+20+20+20+40+40+80=240

如果链表个数非常庞大时,这个该改善还是非常明显的。

实现代码:

public ListNode mergeKLists(ListNode[] lists) {
    if(lists.length==0) return null;
    // 从外向内合并首尾两个链表
    int rightIndex=lists.length-1;
    while(rightIndex>0){
        int l=0,r=rightIndex;
        while(l<r){
            lists[l]=merge(lists[l],lists[r]);
            l++;
            r--;
        }
        rightIndex=r;
    }
    return lists[0];
}
ListNode merge(ListNode l1, ListNode l2){
    if(l1==null) return l2;
    if(l2==null) return l1;
    ListNode node;
    if(l1.val<=l2.val){
        node=new ListNode(l1.val);
        node.next = merge(l1.next, l2);
    }else{
        node=new ListNode(l2.val);
        node.next = merge(l1, l2.next);
    }
    return node;
}

本题解法执行时间为3ms。

Runtime: 3 ms, faster than 86.19% of Java online submissions for Merge k Sorted Lists.

Memory Usage: 44.4 MB, less than 23.50% of Java online submissions for Merge k Sorted Lists.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-23-merge-k-sorted-lists-解题思路分析/
Categories: leetcode
kwantong: