合并K个排序列表-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

**难度： Hard**

> 内容描述

```
合并k个已排序的链表，并将其作为一个已排序的列表返回。分析并描述其复杂性。

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
```

## 解题方案

> 思路 1
*****- 时间复杂度：O(NlogK) *****- 空间复杂度：O(N)*****

K为链表的数量，N为所有链表的节点的总个数

此题在于一分一合，将K个有序链表通过二分，拆成两两一组的链表，就变成了leetcode  21题中的合并两个有序链表了，随后将所有链表逐层合并，就像从二叉树的叶子节点开始，不断向上合并，此题就求解完毕了。

此题需要用到的技巧就是二分，以及递归合并两个有序链表（当然迭代合并两个有序列表也是可以的）

Beats 100%

```java
public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    return sort(lists, 0, lists.length - 1);
}

// 二分K个链表
ListNode sort(ListNode[] lists, int lo, int hi) {
    if (lo >= hi) return lists[lo];
    int mid = (hi -lo) / 2 + lo;
    ListNode l1 = sort(lists, lo, mid);
    ListNode l2 = sort(lists, mid + 1, hi);
    return merge(l1, l2);
}

// 合并两个有序链表的递归写法
ListNode merge(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;

if (l1.val < l2.val) {
        l1.next = merge(l1.next, l2);
        return l1;
    }

l2.next = merge(l2.next, l1);
    return l2;
}

```

该分类下的相关小册推荐：

数据结构与算法(上)

编程之道-算法面试(上)

编程之道-算法面试(下)

数据结构与算法之美

业务开发实用算法精讲

算法面试通关 50 讲

数据结构与算法(下)