题目

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

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

暴力法

说来惭愧，本人在初次解题运用的便是暴力解法。
暴力解法的思想主要分为三点：

  • 遍历所有的链表，将所有的节点的值放到一个数组中。
  • 将这个数组排序，然后遍历所有元素得到正确顺序的值。
  • 用遍历得到的值，创建一个新的有序链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    var arr = [];
   lists.forEach(e=>{
       console.log(e == null)
       if(e != null){ 
           while(e.next != null){
               arr.push(e.val);
               e = e.next
           }
           if(e.val != undefined)arr.push(e.val);
       }
   })
    if(arr.length == 0)return null;
    
    arr = arr.sort((a,b)=>{
        return a-b;
    });
    var list = new ListNode(arr[0]);
    var result = list;
    arr.forEach((e,index)=>{
        if(index > 0){
            list.next = new ListNode(e);
            list = list.next;
        }     
    })
    return result;
};

复杂度分析

  • 时间复杂度：O(NlogN) ，其中 NN 是节点的总数目。

    • 遍历所有的值需花费 O(N) 的时间。
    • 一个稳定的排序算法花费 O(NlogN) 的时间。
    • 遍历同时创建新的有序链表花费 O(N) 的时间。

  • 空间复杂度：O(N)。

    • 排序花费 O(N) 空间（这取决于你选择的算法）。
    • 创建一个新的链表花费 O(N) 的空间。

毫无疑问，这种算法是很消耗性能的，思路简单但并不推荐。
下面介绍一下比较高效的分治法。

分治法

  • 将k个链表配对并将同一对中的链表合并。
  • 第一轮合并以后，k个链表被合并成了k/2,平均长度是2N/k，然后是K/4,K/8个链表等等。
  • 重复这一过程，知道我们得到最终的有序链表。


python的代码演示如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        amount = len(lists)
        interval = 1
        while interval < amount:
            for i in range(0, amount - interval, interval * 2):
                lists[i] = self.merge2Lists(lists[i], lists[i + interval])
            interval *= 2
        return lists[0] if amount > 0 else lists

    def merge2Lists(self, l1, l2):
        head = point = ListNode(0)
        while l1 and l2:
            if l1.val <= l2.val:
                point.next = l1
                l1 = l1.next
            else:
                point.next = l2
                l2 = l1
                l1 = point.next.next
            point = point.next
        if not l1:
            point.next=l2
        else:
            point.next=l1
        return head.next

复杂度分析

  • 时间复杂度： O(Nlogk) ，其中 k 是链表的数目。

    • 我们可以在 O(n) 的时间内合并两个有序链表，其中 nn 是两个链表中的总节点数。
    • 将所有的合并进程加起来，我们可以得到：
      $$ O\big(\sum_{i=1}^{log_2k}N \big)=O(Nlogk) $$

  • 空间复杂度：O(1)

    • 我们可以用 O(1) 的空间实现两个有序链表的合并。