難度：高

先來看一下兩個有序鏈表如何歸并
時間 O(N) 空間 O(1)

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 創(chuàng)建一個dummy頭，從后面開始接
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        // 依次比較拼接
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        // 把剩余的全拼上去
        if(l1 == null){
            curr.next = l2;
        } else if (l2 == null){
            curr.next = l1;
        }
        return dummy.next;
    }
}

k個鏈表歸并

復(fù)雜度
時間 O(NlogK) 空間 O(K)

思路一：
最簡單的方法就是，對于每次插入，遍歷這K個列表的最前面的元素，找出K個中最小的再加入到結(jié)果中。
不過如果用一個優(yōu)先隊列（堆），將這K個元素加入再找堆頂元素，每次插入只要logK的復(fù)雜度。當(dāng)拿出堆頂元素后，再將它所在鏈表的下一個元素拿出來，放到堆中。這樣直到所有鏈表都被拿完，歸并也就完成了。
因為堆中是鏈表節(jié)點，我們在初始化堆時還要新建一個Comparator的類。

解法

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        ListNode dummy = new ListNode(0);
        PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(11, new Comparator<ListNode>(){
            public int compare(ListNode n1, ListNode n2){
                return n1.val - n2.val;
            }
        });
        // 初始化大小為k的堆
        for(int i = 0; i < lists.length; i++){
            if(lists[i] != null) q.offer(lists[i]);
        }
        ListNode curr = dummy;
        while(!q.isEmpty()){
            // 拿出堆頂元素
            curr.next = q.poll();
            curr = curr.next;
            // 將堆頂元素的下一個加入堆中
            if(curr.next != null){
                q.offer(curr.next);    
            }
        }
        return dummy.next;
    }
}

思路二：
對鏈表進行兩兩合并，兩條鏈表的合并復(fù)雜度為O(l + k)，l和k分別代表了兩條鏈表的元素個數(shù)，那么最終的復(fù)雜度為O(n)（n為元素總數(shù)）。

public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists.isEmpty())
            return null;
        return merge(lists, 0, lists.size() - 1);
    }

    public ListNode merge(List<ListNode> lists, int start, int end) {
        if (start == end)
            return lists.get(start);
        int mid = (start + end) / 2;
        ListNode one = merge(lists, start, mid);
        ListNode two = merge(lists, mid + 1, end);
        return mergeTwoLists(one, two);
    }

    public ListNode mergeTwoLists(ListNode node1, ListNode node2) {
        ListNode head = new ListNode(-1), node = head;
        while (node1 != null && node2 != null) {
            if (node1.val < node2.val) {
                node.next = node1;
                node1 = node1.next;
            } else {
                node.next = node2;
                node2 = node2.next;
            }
            node = node.next;
        }
        if (node1 == null && node2 != null) {
            node.next = node2;
        } else if (node1 != null && node2 == null) {
            node.next = node1;
        }
        return head.next;
    }
}