力扣---23. 合并 K 个升序链表-526互联

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

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

示例 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：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

暴力法，直接遍历，每次取值最小的节点加入，然后该节点指向 next，直到所有节点都为 null

分治法：每次将两个 ListNode 合并成一条，直到所有的 ListNode 全都合并成一条。

优先队列：将所有的节点都存入优先队列中，重写比较器使之可以比较链表节点的大小。

优先队列：

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head = new ListNode(Integer.MIN_VALUE);
        ListNode node = head;
        PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> (a.val - b.val));
        for (ListNode tem : lists) {
            if (tem != null) {
                queue.add(tem);
            }
        }
        while (!queue.isEmpty()) {
            ListNode tem = queue.poll();
            node.next = tem;
            node = node.next;
            tem = tem.next;
            if (tem != null) {
                queue.add(tem);
            }
        }
        return head.next;
    }
}

归并：

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        int len = (lists.length + 1) / 2;
        while (lists.length > 1) {
//            归并，两两进行合并，如果长度为单数，则直接放到后面合并即可。
            ListNode[] nodes = new ListNode[len];
            if ((lists.length & 1) == 0) {
                for (int i = 0; i < len; i++) {
                    nodes[i] = mergeList(lists[i * 2], lists[i * 2 + 1]);
                }
            } else {
                for (int i = 0; i < len - 1; i++) {
                    nodes[i] = mergeList(lists[i * 2], lists[i * 2 + 1]);
                }
                nodes[len - 1] = lists[lists.length - 1];
            }
            lists = nodes;
            len = (lists.length + 1) / 2;
        }
        return lists[0];
    }

    /**
     * 合并两链表
     */

    public ListNode mergeList(ListNode node1, ListNode node2) {
        if (node1 == null) {
            return node2;
        } else if (node2 == null) {
            return node1;
        }
        ListNode head;
        if (node1.val > node2.val) {
            head = node2;
            node2 = node2.next;
        } else {
            head = node1;
            node1 = node1.next;
        }
        ListNode node = head;
        while (node1 != null && node2 != null) {
            if (node1.val > node2.val) {
                node.next = node2;
                node2 = node2.next;
            } else {
                node.next = node1;
                node1 = node1.next;
            }
            node = node.next;

        }
        node.next = node1 == null ? node2 : node1;
        return head;
    }
}