題目來源于 LeetCode 第 23 號問題：合并 K 個排序鏈表。

該題在 LeetCode 官網(wǎng)上有關(guān)于鏈表的問題中標(biāo)注為最難的一道題目：難度為 Hard ，通過率在鏈表 Hard 級別目前最低。

題目描述

合并 k 個排序鏈表，返回合并后的排序鏈表。請分析和描述算法的復(fù)雜度。

示例:

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

輸入

圖一

輸出

圖二

題目分析一

這里需要將這 k 個排序鏈表整合成一個排序鏈表，也就是說有多個輸入，一個輸出，類似于漏斗一樣的概念。

因此，可以利用最小堆的概念。如果你對堆的概念不熟悉，可以戳這先了解一下~

取每個 Linked List 的最小節(jié)點放入一個 heap 中，排序成最小堆。然后取出堆頂最小的元素，放入輸出的合并 List 中，然后將該節(jié)點在其對應(yīng)的 List 中的下一個節(jié)點插入到 heap 中，循環(huán)上面步驟，以此類推直到全部節(jié)點都經(jīng)過 heap。

由于 heap 的大小為始終為 k ，而每次插入的復(fù)雜度是 logk ，一共插入了 nk 個節(jié)點。時間復(fù)雜度為 O(nklogk)，空間復(fù)雜度為O(k)。

動畫演示

動畫演示

代碼實現(xiàn)

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        //用heap(堆)這種數(shù)據(jù)結(jié)構(gòu)，也就是 java 里面的 PriorityQueue
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
            public int compare(ListNode a, ListNode b) {
                return a.val-b.val;
            }
        });
        ListNode ret = null, cur = null;
        for(ListNode node: lists) {
            if(null != node) {
                pq.add(node);    
            }
        }
        while(!pq.isEmpty()) {
            ListNode node = pq.poll();
            if(null == ret) {
                ret = cur = node;
            }
            else {
                cur = cur.next = node;
            }
            if(null != node.next) {
                pq.add(node.next);    
            }
        }
        return ret;
    }
}

題目分析二

這道題需要合并 k 個有序鏈表，并且最終合并出來的結(jié)果也必須是有序的。如果一開始沒有頭緒的話，可以先從簡單的開始：合并 兩 個有序鏈表。

合并兩個有序鏈表：將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。

示例：

輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

這道題目按照題目描述做下去就行：新建一個鏈表，比較原始兩個鏈表中的元素值，把較小的那個鏈到新鏈表中即可。需要注意的一點時由于兩個輸入鏈表的長度可能不同，所以最終會有一個鏈表先完成插入所有元素，則直接另一個未完成的鏈表直接鏈入新鏈表的末尾。

所以代碼實現(xiàn)很容易寫：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //新建鏈表
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            } else {
                cur.next = l2;
                cur = cur.next;
                l2 = l2.next;
            }
        }
        // 注意點：當(dāng)有鏈表為空時，直接連接另一條鏈表
        if (l1 == null) {
            cur.next = l2;
        } else {
            cur.next = l1;
        }
        return dummyHead.next;
    }

現(xiàn)在回到一開始的題目：合并 K 個排序鏈表。

合并 K 個排序鏈表 與 合并兩個有序鏈表 的區(qū)別點在于操作有序鏈表的數(shù)量上，因此完全可以按照上面的代碼思路來實現(xiàn)合并 K 個排序鏈表。

這里可以參考 **歸并排序 **的分治思想，將這 K 個鏈表先劃分為兩個 K/2 個鏈表，處理它們的合并，然后不停的往下劃分，直到劃分成只有一個或兩個鏈表的任務(wù)，開始合并。

歸并-分治

代碼實現(xiàn)

根據(jù)上面的動畫，實現(xiàn)代碼非常簡單也容易理解，先劃分，直到不能劃分下去，然后開始合并。

class Solution {
    public ListNode mergeKLists(ListNode[] lists){
        if(lists.length == 0)
            return null;
        if(lists.length == 1)
            return lists[0];
        if(lists.length == 2){
           return mergeTwoLists(lists[0],lists[1]);
        }

        int mid = lists.length/2;
        ListNode[] l1 = new ListNode[mid];
        for(int i = 0; i < mid; i++){
            l1[i] = lists[i];
        }

        ListNode[] l2 = new ListNode[lists.length-mid];
        for(int i = mid,j=0; i < lists.length; i++,j++){
            l2[j] = lists[i];
        }

        return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));

    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode head = null;
        if (l1.val <= l2.val){
            head = l1;
            head.next = mergeTwoLists(l1.next, l2);
        } else {
            head = l2;
            head.next = mergeTwoLists(l1, l2.next);
        }
        return head;
    }
}

歡迎前往

個人網(wǎng)站：https://www.cxyxiaowu.com

公眾號：五分鐘學(xué)算法