Leetcode 23. 合并K个升序链表

image.png

解法1. 使用优先级队列

第一步：定义一个最小堆（Java使用PriorityQueue即可）

第二步：将链表数组中所有链表头节点入添加到最小堆中

第三步：合并。

step1：定义一个dummyNode（虚拟节点），作为最终有序链表的前驱节点；

step2：遍历最小堆，每次取出最小堆中的堆顶元素node（即当前堆中最小的元素），添加至dummyNode的下一个节点中；

step3：同时检查下当前node是否有下一个节点，有则添加到最小堆中，然后继续step2，遍历最小堆中下一个最小元素。

最终返回dummyNode的下一个节点，即为答案

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        // 使用优先队列作为最小堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, (a, b) -> a.val - b.val);

        // 将lists中所有head添加到pq中
        for (ListNode head : lists) {
            if (head != null) pq.add(head);
        }

        // 合并
        ListNode dummyNode = new ListNode(-1);
        ListNode curr = dummyNode;
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            curr.next = node;
            // 当前从队列中取出来的节点如果存在下一个节点，继续入队排序
            if (node.next != null) {
                pq.add(node.next);
            }
            curr = curr.next;
        }
        return dummyNode.next;
    }
}

解法2. 分治法（类似归并排序）

第一步：跟归并排序一样，第一步先找到当前数组的中间位置mid；

第二步：找到mid之后，分别递归调用继续对以mid为分界的左右两段子序列做拆分，直到不可拆；

第三步：按升序排列，对所有拆分后的链表做两两的回溯合并（合并的代码：相当于力扣第 21 题【合并两个有序链表】），合并结果即为答案。

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
        // 找mid
        int mid = (l + r) >> 1;
        // 继续拆、继续合并
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    public ListNode mergeTwoLists(ListNode left, ListNode right) {
        if (left == null || right == null) {
            return left != null ? left : right;
        }
        ListNode dummyNode = new ListNode(0);
        ListNode curr = dummyNode, l = left, r = right;
        while (l != null && r != null) {
            if (l.val < r.val) {
                curr.next = l;
                l = l.next;
            } else {
                curr.next = r;
                r = r.next;
            }
            curr = curr.next;
        }
        curr.next = (l != null ? l : r);
        return dummyNode.next;
    }
}