Leetcode算法Java全解答--23. 合并K个排序链表

短命女 2022-04-15 04:59 149阅读 0赞

# Leetcode算法Java全解答–23. 合并K个排序链表 #

### 文章目录 ###

*  Leetcode算法Java全解答--23. 合并K个排序链表
 *   *  题目
     *  想法
     *  结果
     *  总结
     *  代码
     *   *  我的答案
         *  大佬们的答案
         *  测试用例
     *  其他

## 题目 ##

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

示例：

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

## 想法 ##

1.  复制 021-合并两个有序列表的思路，去遍历lists中的每个ListNode，然后对比各项的值

链接 [合并两个有序列表][Link 1]

参考mergeKLists方法

复杂度 n的n次方/n

1.  使用两两合并的方式，左边和右边合并，

参考better方法

每执行一次while的循环体，需要合并的链表数就减半，因此while循环体执行次数为logk。

每次执行循环体的时间开销：第一次执行循环体：k/2次合并2个长度为n的链表，

时间复杂度为O(nk)；第二次执行循环体：k/4次合并2个长度为2n的链表，

时间复杂度依然为O(nk)。以此类推，每次执行循环体的时间开销都为O(nk)。

复杂度O(nklogk)/n

## 结果 ##

超过10%的测试案例

复杂度：n的n次方/n

## 总结 ##

直接套用了原来的解题思路，没有开拓新的方法

## 代码 ##

### 我的答案 ###

/**************************************
         * 题目
         合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
    
         示例:
    
         输入:
         [
         1->4->5,
         1->3->4,
         2->6
         ]
         输出: 1->1->2->3->4->4->5->6
         **************************************/
    
        /**************************************
         *
         * 想法：
         *      1. 复制 021-合并两个有序列表 的思路，去遍历lists中的每个ListNode，然后对比各项的值
         *          链接合并两个有序列表
         *          参考mergeKLists方法
         *          复杂度 n的n次方/n
         *      2. 使用两两合并的方式，左边和右边合并，
         *          参考better方法
         *          每执行一次while的循环体，需要合并的链表数就减半，因此while循环体执行次数为logk。
         *          每次执行循环体的时间开销：第一次执行循环体：k/2次合并2个长度为n的链表，
         *          时间复杂度为O(nk)；第二次执行循环体：k/4次合并2个长度为2n的链表，
         *          时间复杂度依然为O(nk)。以此类推，每次执行循环体的时间开销都为O(nk)。
         *          复杂度O(nklogk)/n
         *
         * 我的做法
         *      超过10%的测试案例
         *      复杂度：n的n次方/n
         * 代码执行过程：
         *
         * 总结：
         *      直接套用了原来的解题思路，没有开拓新的方法
         * ***********************************/
        public ListNode mergeKLists(ListNode[] lists) {
    
            ListNode result = new ListNode(0);
            ListNode cur = result;
    
            while (true) {
                Integer tmpMin = null;
                int tmpIndex = -1;
                for (int i = 0; i < lists.length; i++) {
                    ListNode listNode = lists[i];
                    if (listNode == null) {
                        continue;
                    }
                    if (tmpMin == null) {
                        tmpMin = listNode.val;
                        tmpIndex = i;
                    } else {
                        if (tmpMin > listNode.val) {
                            tmpMin = listNode.val;
                            tmpIndex = i;
                        }
                    }
                }
                if (tmpIndex == -1) {
                    break;
                }
                cur.next = lists[tmpIndex];
                lists[tmpIndex] = lists[tmpIndex].next;
                cur = cur.next;
            }
    
            return result.next;
        }

### 大佬们的答案 ###

/**************************************
         * 比我好的答案 better
         * ***********************************/
        public ListNode better(ListNode[] lists) {
            if (lists.length == 0) {
                return null;
            }
            return helper(lists, 0, lists.length - 1);
        }
    
        private ListNode helper(ListNode[] lists, int low, int high) {
            if (low == high) {
                return lists[low];
            }
            int mid = low + (high - low) / 2;
            ListNode leftNodes = helper(lists, low, mid);
            ListNode rightNodes = helper(lists, mid + 1, high);
            return mergeTwo(leftNodes, rightNodes);
    
        }
    
        private ListNode mergeTwo(ListNode list1, ListNode list2) {
            ListNode dummy = new ListNode(0);
            ListNode temp = dummy;
            while (null != list1 && null != list2) {
                if (list1.val < list2.val) {
                    temp.next = list1;
                    list1 = list1.next;
                } else {
                    temp.next = list2;
                    list2 = list2.next;
                }
                temp = temp.next;
            }
            if (null != list1) {
                temp.next = list1;
            }
            if (null != list2) {
                temp.next = list2;
            }
            return dummy.next;
        }

### 测试用例 ###

@Test
        public void test023() {
            // 创建测试案例
            ListNode listNode11 = new ListNode(1);
            ListNode listNode12 = new ListNode(2);
            ListNode listNode13 = new ListNode(4);
            listNode11.next = listNode12;
            listNode12.next = listNode13;
    
            ListNode listNode21 = new ListNode(1);
            ListNode listNode22 = new ListNode(3);
            ListNode listNode23 = new ListNode(4);
            listNode21.next = listNode22;
            listNode22.next = listNode23;
    
            ListNode[] nodeList1 = new ListNode[] { listNode11, listNode21 };
    
            // 测试案例期望值
            ListNode expResult1 = new ListNode(1);
            ListNode expResult12 = new ListNode(1);
            ListNode expResult13 = new ListNode(2);
            ListNode expResult15 = new ListNode(3);
            ListNode expResult16 = new ListNode(4);
            ListNode expResult17 = new ListNode(4);
            expResult1.next = expResult12;
            expResult12.next = expResult13;
            expResult13.next = expResult15;
            expResult15.next = expResult16;
            expResult16.next = expResult17;
    
            Solution023 solution023 = new Solution023();
    
            ListNode result1 = solution023.mergeKLists(nodeList1);
    
            Assert.assertEquals(expResult1.toArray(), result1.toArray());
        }

## 其他 ##

代码托管码云地址：[https://gitee.com/lizhaoandroid/LeetCodeAll.git][https_gitee.com_lizhaoandroid_LeetCodeAll.git]

查看其他内容可以点击专栏或者我的博客哈：[https://blog.csdn.net/cmqwan][https_blog.csdn.net_cmqwan]

“大佬们的答案” 标签来自leetcode，侵权请联系我进行删改

如有疑问请联系，联系方式：QQ3060507060

[Link 1]: https://blog.csdn.net/cmqwan/article/details/84329796
[https_gitee.com_lizhaoandroid_LeetCodeAll.git]: https://gitee.com/lizhaoandroid/LeetCodeAll.git
[https_blog.csdn.net_cmqwan]: https://blog.csdn.net/cmqwan