算法-合并 K 个升序链表

1. 合并多个链表问题

给定一个链表数组，每个链表都已经按升序排列，将所有链表合并到一个升序链表中，返回合并后的链表，leetcode 原题

示例 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. 解法

2.1 优先权队列

1. 取当前每个链表头部元素，将其投入优先权队列（小顶堆）
2. 遍历优先权队列，每次取队列头部元素（即当前所有链表元素中 val 最小的元素），将其合并到结果链表，并将其下一个节点入队即可

 public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
        for (ListNode root : lists) {
            if (null != root) {
                queue.offer(root);
            }
        }
        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        while (!queue.isEmpty()) {
            ListNode min = queue.poll();
            tail.next = min;
            tail = tail.next;
            if (null != min.next) {
                queue.offer(min.next);
            }
        }

        return dummyHead.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.2 分治法

1. 递归将有序链表数组分割，直至分治为一个个单独链表
2. 将有序链表两两合并，可参考 算法-合并两个有序链表，递归收束则一层一层完成全部链表的合并

  public ListNode mergeKLists(ListNode[] lists) {
        if (null == lists || 0 == lists.length) {
            return null;
        }
        return merge(lists, 0, lists.length - 1);
    }
    
    public ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        if (left > right) {
            return null;
        }
        int mid = left + ((right - left) >> 1);
        ListNode leftNode = merge(lists, left, mid);
        ListNode rightNode = merge(lists, mid + 1, right);
        return mergeTwoList(leftNode, rightNode);
    }

    public ListNode mergeTwoList(ListNode leftNode, ListNode rightNode) {
        if (null == leftNode) {
            return rightNode;
        }
        if (null == rightNode) {
            return leftNode;
        }
        ListNode dummyHead = new ListNode(0);
        ListNode root = dummyHead;
        while (null != leftNode && null != rightNode) {
            if (leftNode.val < rightNode.val) {
                root.next = leftNode;
                leftNode = leftNode.next;
            } else {
                root.next = rightNode;
                rightNode = rightNode.next;
            }
            root = root.next;

        }

        root.next = leftNode == null ? rightNode : leftNode;
        return dummyHead.next;
    }
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