LC.P23[合并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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> q = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode node : lists) {
            if (node != null) {
                q.offer(node);
            }
        }
        ListNode dummy = new ListNode(), cur = dummy;
        while (!q.isEmpty()) {
            ListNode node = q.poll();
            if (node.next != null) q.offer(node.next);
            cur.next = node;
            cur = cur.next;
        }
        return dummy.next;
    }
}
  • 时间复杂度：$O(nlogk)$，其中$k$为$list$中元素个数
  • 空间复杂度：$O(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
32
33
34
35
36
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) return lists[l];
        else if (l > r) return null;
        int mid = l + r >> 1;
        ListNode p1 = merge(lists, l, mid);
        ListNode p2 = merge(lists, mid + 1, r);
        return mergeTwoList(p1, p2);
    }

    private ListNode mergeTwoList(ListNode p1, ListNode p2) {
        if (p1 == null) return p2;
        else if (p2 == null) return p1;
        if (p1.val < p2.val) {
            p1.next = mergeTwoList(p1.next, p2);
            return p1;
        } else {
            p2.next = mergeTwoList(p1, p2.next);
            return p2;
        }
    }
}
  • 时间复杂度：$O(nlogk)$，其中$k$为$list$中元素个数
  • 空间复杂度：$O(logk)$