Leetcode 23. 合并K個升序鏈表

image.png

解法1. 使用優(yōu)先級隊列

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

第二步：將鏈表數(shù)組中所有鏈表頭節(jié)點入添加到最小堆中

第三步：合并。

step1：定義一個dummyNode（虛擬節(jié)點），作為最終有序鏈表的前驅(qū)節(jié)點；

step2：遍歷最小堆，每次取出最小堆中的堆頂元素node（即當(dāng)前堆中最小的元素），添加至dummyNode的下一個節(jié)點中；

step3：同時檢查下當(dāng)前node是否有下一個節(jié)點，有則添加到最小堆中，然后繼續(xù)step2，遍歷最小堆中下一個最小元素。

最終返回dummyNode的下一個節(jié)點，即為答案

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

        // 使用優(yōu)先隊列作為最小堆
        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;
            // 當(dāng)前從隊列中取出來的節(jié)點如果存在下一個節(jié)點，繼續(xù)入隊排序
            if (node.next != null) {
                pq.add(node.next);
            }
            curr = curr.next;
        }
        return dummyNode.next;
    }
}

解法2. 分治法（類似歸并排序）

第一步：跟歸并排序一樣，第一步先找到當(dāng)前數(shù)組的中間位置mid；

第二步：找到mid之后，分別遞歸調(diào)用繼續(xù)對以mid為分界的左右兩段子序列做拆分，直到不可拆；

第三步：按升序排列，對所有拆分后的鏈表做兩兩的回溯合并（合并的代碼：相當(dāng)于力扣第 21 題【合并兩個有序鏈表】），合并結(jié)果即為答案。

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;
        // 繼續(xù)拆、繼續(xù)合并
        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;
    }
}