原题

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

示例:

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

解法

思想

逐一比较或两两合并（分治）。

代码

逐一比较：时间复杂度O(nm)（n为链表个数，m为链表最大长度）

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head = new ListNode(0);
        ListNode cur = head;
        int min = -1;
        int leftCount = lists.length;
        while(leftCount>0){
            for(int i = 0;i<leftCount;i++){
                if(lists[i]!=null&&(min==-1||lists[i].val<lists[min].val)) min = i;
            }
            if(min == -1){
                leftCount--;
                break;
            }
            ListNode node = lists[min];
            if(lists[min].next==null){
                lists[min]=lists[leftCount-1];
                leftCount--;
            }else lists[min] = lists[min].next;
            cur.next = node;
            cur = cur.next;
            min = -1;
        }
        return head.next;
    }
}

两两合并：时间复杂度O(nm/2)（n为链表个数，m为链表最大长度）

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        if (len == 0) {
            return null;
        }
        // 将n个链表以中间为对称，合并
        while(len>1) {
            for (int i=0; i<len/2; i++) {
                lists[i] = mergeTwoListsForK(lists[i], lists[len-1-i]);
            }
            len = (len+1)/2;
        }
        return lists[0];
    }

    private ListNode mergeTwoListsForK(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode p = head;
        while(l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        if (l1 != null) {
            p.next = l1;
        } else if (l2 != null) {
            p.next = l2;
        }
        return head.next;
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode23-%e5%90%88%e5%b9%b6k%e4%b8%aa%e6%8e%92%e5%ba%8f%e9%93%be%e8%a1%a8/