code4offer-23

Analyse

借鉴merge sort的思想，先2个1组合并成k/2组，对这合并好的k/2组继续2个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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode listA, ListNode listB) {
        ListNode head = new ListNode();
        ListNode tmpA = listA, tmpB = listB;
        ListNode cur = head;

        while (tmpA != null && tmpB != null) {
            // 找到两个链表的较小值append到head
            if (tmpA.val > tmpB.val) {
                cur.next = tmpB;
                tmpB = tmpB.next;
            } else {
                cur.next = tmpA;
                tmpA = tmpA.next;
            }

            cur = cur.next;
        }

        cur.next = (tmpA == null) ? tmpB : tmpA;

        return head.next;
    }


    public ListNode helper(ListNode[] lists, int left, int right) {
        if (left >= right) return lists[left];

        int mid = (left + (right - left) / 2);

        return mergeTwoLists(helper(lists, left, mid), helper(lists, mid+1, right));
    }

    // k个list 分成每组两个再合并，类似merge sort
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;

        return helper(lists, 0, lists.length - 1);
    }
}

利用优先队列来合并

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) {
    if (lists.length == 0) return null;

    // 默认最小堆
    PriorityQueue<ListNode> queue = new PriorityQueue<>((x,y) -> x.val - y.val);

    ListNode res = new ListNode(0);
    ListNode cur = res;
    for (ListNode node : lists) {
        if (node != null) queue.offer(node);
    }

    while (!queue.isEmpty()) {
        ListNode tmp = queue.poll();
        cur.next = tmp;
        cur = cur.next;
        if (tmp.next != null) queue.offer(tmp.next);
    }

    return res.next;
}