Day16 合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

https://leetcode-cn.com/problems/merge-k-sorted-lists/

示例1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例2：

输入：lists = []
输出：[]

示例3：

输入：lists = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i] [j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4

Java解法

思路：

• 第一次尝试下困难题，与合并两个有序链表大致相同，尝试用下相同的解法
• 取出每个节点的头节点，调用比较决出头结点，在替换放入下一次比较
• 果然简单，一把过 还是效率差很多
• 使用while 优化内存，但时间还是较差(官方解的分治排序效率不错)

package sj.shimmer.algorithm.ten_2;

import sj.shimmer.algorithm.ListNode;

/**
 * Created by SJ on 2021/2/9.
 */

class D16 {
    public static void main(String[] args) {
        ListNode n1 = ListNode.createNode(new int[]{1,4,5});
        ListNode n2 = ListNode.createNode(new int[]{1,3,4});
        ListNode n3 = ListNode.createNode(new int[]{2,6});
        ListNode n4 = ListNode.createNode(new int[]{});
//        System.out.println(mergeKLists(new ListNode[]{n1,n2,n3}));
//        System.out.println(mergeKLists(new ListNode[]{}));
//        System.out.println(mergeKLists(new ListNode[]{n4}));

        System.out.println(mergeKLists2(new ListNode[]{n1,n2,n3}));
        System.out.println(mergeKLists2(new ListNode[]{}));
        System.out.println(mergeKLists2(new ListNode[]{n4}));
    }
    public static ListNode mergeKLists2(ListNode[] lists) {
        ListNode preHead = new ListNode();
        ListNode pre = preHead;
        int minIndex = getMin(lists);
        while (minIndex!=-1) {
            ListNode node = lists[minIndex];
            pre.next = node;
            pre = pre.next;
            lists[minIndex] = node.next;
            minIndex = getMin(lists);
        }
        return preHead.next;
    }
    public static ListNode mergeKLists(ListNode[] lists) {
        ListNode head = null;
        int minIndex = getMin(lists);
        if (minIndex==-1) {
            return null;
        }
        head = lists[minIndex];
        lists[minIndex] = head.next;
        head.next = mergeKLists(lists);
        return head;
    }
    public static int getMin(ListNode[] lists) {
        ListNode min = null;
        int minIndex = -1;

        for (int i = 0; i < lists.length; i++) {

            if (lists[i] == null) {
                continue;
            }
            if (min == null||min.val>lists[i].val) {
                min = lists[i];
                minIndex = i;
            }
        }
        return minIndex;
    }
}

image image

官方解

https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/he-bing-kge-pai-xu-lian-biao-by-leetcode-solutio-2/

1. 顺序合并

   利用已有的合并两个有序链表的操作，循环合并

   • 时间复杂度： O(k^2 *n)
   • 空间复杂度：O(1)

2. 分治合并

   上一合并的优化，采用分治思想，同时分别合并两个链表

    public static ListNode merge(ListNode[] lists,int l,int r) {
           if (l==r) {
               return lists[l];
           }
           if (l>r) {
               return null;
           }
           int mid = (r-l)/2+l;
           return mergeTwoLists(merge(lists,l,mid),merge(lists, mid+1, r));
       }
   
   
       public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
           ListNode prehead = new ListNode(-1);
   
           ListNode prev = prehead;
           while (l1 != null && l2 != null) {
               if (l1.val <= l2.val) {
                   prev.next = l1;
                   l1 = l1.next;
               } else {
                   prev.next = l2;
                   l2 = l2.next;
               }
               prev = prev.next;
           }
   
           // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
           prev.next = l1 == null ? l2 : l1;
   
           return prehead.next;
       }
   

   image

   • 时间复杂度为O(kn×logk)。
   • 空间复杂度：递归会使用到 O(logk)