WangBa's Blog

0023. Merge k Sorted Lists

LeetCode真的难系列

发布于：2020年10月14日
次浏览

23. Merge k Sorted Lists Hard

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

1
2
3
4
5
6
7
8
9
10
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

1
2
Input: lists = []
Output: []

Example 3:

1
2
Input: lists = [[]]
Output: []

Constraints:

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length won’t exceed 10^4.

思路：

思路一：暴力解法

遍历链表数组中的每一个链表，在每一个链表中继续遍历，将所有的结果都存在数组中，再进行一次快速排序，最后再把数组中的每个结点组装成链表即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode mergeKLists(ListNode[] lists) {
    List<Integer> res = new ArrayList<>();
    for (ListNode listNode : lists) {
        while (listNode != null) {
            res.add(listNode.val);
            listNode = listNode.next;
        }
    }
    Collections.sort(res);
    ListNode head = new ListNode(-1);
    ListNode ans = head;
    for (int i : res) {
        ListNode listNode = new ListNode(i);
        head.next  = listNode;
        head = head.next;
    }
    head.next = null;
    return ans.next;
}

时间复杂度：O(nlogn)，n 为所有结点数

空间复杂度：O(n)

思路二：列比较

利用每个链表数组中的链表是有序的，则每次拿到最小的结点加入新的链表中，每个链表数组中的链表头的值一定是最小的

代码：

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
public ListNode mergeKLists(ListNode[] lists) {
    // 2. 列比较
    // 最小索引
    int minIndex = 0;
    ListNode head = new ListNode(-1);
    ListNode res = head;

    while (true) {
        boolean isCompleted = true;
        int min = Integer.MAX_VALUE;
        // 遍历一遍链表数组找到数值最小的结点
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                if (lists[i].val < min) {
                    minIndex = i;
                    min = lists[i].val;
                }
                isCompleted = false;
            }
        }

        // 当所有的链表全部遍历完了，while 循环结束
        if (isCompleted) break;
        head.next = lists[minIndex];
        head = head.next;
        lists[minIndex] = lists[minIndex].next;
    }
    head.next = null;
    return res.next;
}

时间复杂度：O(m * n)，m 为最长链表的长度；n 为链表数组长度

空间复杂度：O(1)

思路三：优先队列

在上面的思路中，每次都是找到链表数组中最小的结点，再加入新链表中，在上面使用的直接遍历的方式，在这里可以采用优先队列的方式，优先队列是基于堆实现的，具体来说就是小/大根(顶)堆，只需要将每个链表的头结点放入，会自动进行大小比较，出队列是就是最小/最大

代码：

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
public ListNode mergeKLists(ListNode[] lists) {
    // 优先队列中默认就是小根堆
    PriorityQueue<ListNode> priorityQueue = new PriorityQueue<ListNode>(Comparator.comparing(n -> n.val));
    
    // 将每个结点的的头结点加入优先队列
    for (int i = 0; i < lists.length; i++) {
        if (lists[i] != null) {
            priorityQueue.add(lists[i]);
        }
    }

    ListNode head = new ListNode(-1);
    ListNode res = head;

    while (!priorityQueue.isEmpty()) {
        // 出队列时就是最小值先出来的
        head.next = priorityQueue.poll();
        head = head.next;
        // 将出队列的后面那个值加入优先队列
        if (head.next != null) {
            priorityQueue.add(head.next);
        }
    }
    return res.next;
}

时间复杂度：O(nlogk)，n 表示所有的结点书数，logk 表示每个结点的入队、出队

空间复杂度：O(k)，k 表示链表数组的长度；在 Java 中优先队列是有默认值的

思路四：两两合并

在0021. Merge Two Sorted Lists中，已经实现过两个有序链表的合并，本题也可以参考这个思路：首先将链表 0 和链表 1 合并，合并成新的链表 a，在和链表 2 进行合并 ……

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public ListNode mergeKLists(ListNode[] lists) {
    // 4. 两两合并
    ListNode temp = null;
    for (int i = 0; i < lists.length; i++) {
        temp = mergeTwoLists(temp, lists[i]);
    }
    return temp;
}

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

思路五：二分法两两合并

在上面思路五中，合并的思路是：先是合并第一个和第二个，合并为新的后，再和第三个进行合并，这样的效率有点低

这个思路也是可以优化的，使用二分法：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    return merge(lists, 0 , lists.length - 1);
}

private ListNode merge(ListNode[] lists, int left, int right) {
    if (left == right) return lists[left];
    int mid = left + (right - left) / 2;
    ListNode l = merge(lists, left, mid);
    ListNode r = merge(lists, mid + 1, right);
    return mergeTwoLists(l , r);
}

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

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://wangba.me/2020/10/14/0023-Merge-k-Sorted-Lists/

更新于：2020年10月14日

Leetcode

LinkedList

评论