関小君刷题记

题目大意：

合并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-解题思路分析/