【Leetcode】23.合并K个升序链表

23. 合并K个升序链表

题目

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

 

示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

方法一（优先队列）

之前曾用过归并排序的思路解决过合并2个升序链表的问题。这个题我们也可以使用相同的思路，用k个指针分别指向这k个链表的节点，每次都取这k个节点中值最小的一个放到我们的结果链表中去。

既然我们每次都要在一系列值中找到最小的那个，很自然就会想到用一个最小堆来实现：

  • 准备一个小根堆，将lists中的所有链表加入到堆中
  • 每次从小根堆中取出一个链表，将这个链表的头挂到结果链表中去
  • 将上述链表头节点之后的剩余部分再放入堆中，相当于这个链表的cur指针向后移了一步。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode mergeKLists(ListNode[] lists) {
    if(lists == null || lists.length == 0)
        return null;
    PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
    for(ListNode list : lists){
        if(list != null)
            heap.add(list);
    }
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    while(!heap.isEmpty()){
        cur.next = heap.poll();
        cur = cur.next;
        if(cur.next != null)
            heap.add(cur.next);
    }
    return dummy.next;
}
  • 时间复杂度：O(Nlogk)
  • 空间复杂度：O(k)

方法二（分治法）

回顾分治法的基本思想为：将难以解决的大问题分解为多个容易解决的小问题，再逐个解决小问题，最终用小问题的解合并即得到了原大问题的解。

分治法只要考虑以下三点：

  • 分解：将合并k个链表的原问题，分解为合并lists中左半组链表和右半组链表这两个子问题
  • 合并：递归解决上述子问题后，我们得到了两个合并后的链表，这时将二者再归并就是答案。这时，问题已经由归并k个链表，转化为了归并两个链表
  • 递归返回条件：当把子问题分解为最小时，只有一个链表，无需归并，直接返回即可。
    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
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0)
            return null;
        return merge(lists, 0, lists.length - 1);
    }
    //归并lists中索引从start到end间的这些链表
    public ListNode merge(ListNode[] lists, int start, int end){
        if(start == end)
            return lists[start];
        int mid = start + (end - start) / 2;
        ListNode list1 = merge(lists, start, mid);
        ListNode list2 = merge(lists, mid + 1, end);
        return merge2Lists(list1, list2);
    }
    //将问题转化为归并两个链表的问题
    public ListNode merge2Lists(ListNode list1, ListNode list2){
        if(list1 == null && list2 == null)
            return null;
        if(list1 == null)
            return list2;
        if(list2 == null)
            return list1;
        if(list1.val < list2.val){
            list1.next = merge2Lists(list1.next, list2);
            return list1;
        }
        else{
            list2.next = merge2Lists(list2.next, list1);
            return list2;
        }
    }
  • 时间复杂度：O(Nlogk)
  • 空间复杂度：O(1)