合并K个排序链表

题目链接Leecode23

题目描述

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

示例:

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

解题思路

链表节点定义

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

方法一：暴力合并（空间不足）

一个比较直接的思路就是将K个列表中的数据全部提取出来存放在一个顺序容器中，进行排序后在构造一个链表存放这些数据。代码如下：

// java
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        List<Integer> data = new ArrayList<Integer>() ;
        for(int i = 0; i < lists.length; i++){
            ListNode p = lists[i] ;
            while(p != null){
                data.add(p.val) ;
                p = p.next ;
            }
        }

        data.sort(Integer::compareTo) ;
        // 增加一个头节点便于操作
        ListNode head = new ListNode(0) ;
        ListNode it = head ;
        for(int num : data){
            it.next = new ListNode(num) ;
            it = it.next ;
        }
        return head.next ;
    }
};

时间复杂度：，N是K个链表的节点总数，这里使用了快速排序算法，时间复杂度为，收集数据和构造链表都是
空间复杂度：，快速排序的空间复杂度为，收集数据和构造链表都是

方法二：优先队列

因为输入的K个链表都是有序，可以将每个链表的数据值最小的节点存放在一个优先队列中，队列长度最多为K。将队列的第一个节点出队，并且向队列中添加该节点的后继，直到队列为空。把所有的出队节点连接在一起，形成一个新的链表，就是合并后的链表。

// java
class Solution{
    // 自定义ListNode的比较器，按val升序
    private Comparator<ListNode> cl = new Comparator<ListNode>() {
        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val ;
        }
    } ;
    public ListNode mergeKLists(ListNode[] lists)
    {
        // head是辅助空间，不存储数据，记录链表起始节点
        ListNode head = new ListNode(0) ;
        ListNode it   = head ;
        // 优先队列
        PriorityQueue<ListNode> queue = new PriorityQueue<>(cl) ;

        for(ListNode ln : lists){
            queue.add(ln) ;
        }

        while(queue.isEmpty() != true){
            ListNode temp = queue.poll() ;
            if(temp.next != null)
                queue.add(temp.next) ;
            it.next = temp ;
            it = it.next ;
        }

        return head.next ;
    }
}

时间复杂度：考虑优先队列中的元素不超过 K 个，那么插入和删除的时间代价为 ，这里最多有K*N 个点，对于每个点都被插入删除各一次，故总的时间代价即渐进时间复杂度为 。
空间复杂度：这里用了优先队列，优先队列中的元素不超过 K个，故渐进空间复杂度为

方法三：顺序合并

在进行K个有序链表的合并时，首先考虑更简单的问题：如何合并两个有序链表？为了减少内存的使用，不再申请空间存放数据，而是修改指针完成合并。一个比较简单的思路就是，同时遍历两个有序链表a、b，如果a的迭代器指向的数据比b小，那么将该节点附加到新链表的末尾，并且a的迭代器前进一个位置，b保持不变。否则就是b的迭代器移动。代码如下：

// java
class Solution {
    public ListNode mergeTwoLinks(ListNode pa, ListNode pb){
        ListNode head = new ListNode(0) ;
        ListNode it = head ;
        while(pa != null && pb != null){
            if(pa.val < pb.val){
                it.next = pa ;
                pa = pa.next ;
            }else{
                it.next = pb ;
                pb = pb.next ;
            }
            it = it.next ;
        }
        // 如果还有没遍历的节点，直接附加到新链表上
        it.next = (pa != null) ? pa : pb ;
        return head.next ;
    }
}

从两个链表扩充到K个链表合并，一个相对简单的操作就是设一个新链表引用指向第一个要合并的链表，然后使用上面的mergeTwoLink()函数与第二个链表合并；将得到的新链表与第三个链表合并...以此类推就可以合并K个链表

// java
class Solution {
    public ListNode mergeKLists(ListNode[] lists){
        if(lists.length == 0)
            return null ;
        int size = lists.length ;
        // 记录链表起始位置
        ListNode head = new ListNode(0) ;
        ListNode it   = head ;
        it.next = lists[0] ;
        for(int i = 1;  i < lists.length; i++){
            it.next = mergeTwoLinks(it.next, lists[i]) ;
        }
        return head.next ;
    }
    public ListNode mergeTwoLinks(ListNode pa, ListNode pb){
        // 合并两个链表
    }
}

时间复杂度：假设每个链表的最长长度是 n。在第一次合并后，的长度为 ；第二次合并后， 的长度为 ，第 次合并后， 的长度为 。第 次合并的时间代价是那么总的时间代价为，那么总的时间复杂度为，故渐进时间复杂度为
空间复杂度：没有用到与 k 或者n 规模相关的辅助空间，故渐进空间复杂度为 。

方法四：两两合并

两两合并，顾名思义就是对链表进行配对合并，进行多轮合并，直到数组只剩下一个链表。

// java
class Solution {
      public ListNode mergeKLists(ListNode[] lists) {
        int N = lists.length;

        if (N == 0)
        {
            return null;
        }

        if (N == 1)
        {
            return lists[0];
        }
        if (N == 2) {
            return merge2Lists(lists[0], lists[1]);
        }
        // 也可以写成循环的形式，不用递归而是，复用数组lists
        ListNode[] newLists = new ListNode[(N + 1) / 2];
        for (int i = 0; i < lists.length / 2; i++) {
            newLists[i] = merge2Lists(lists[i], lists[i + N / 2]);
        }

        if (N % 2 != 0) {
            newLists[(N - 1) / 2] = lists[N - 1];
        }
        return mergeKLists(newLists);
    }
    public ListNode mergeTwoLinks(ListNode pa, ListNode pb){
        // 合并两个有序链表
    }
}

时间复杂度：，n是链表长度的最大值，K为链表数量
空间复杂度：