合并K个升序链表

题目

输入：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

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

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

解题方法一

/**
     * 使用优先队列合并
     *
     * 时间复杂度：考虑优先队列中的元素不超过 k 个，那么插入和删除的时间代价为 O(logk)，这里最多有 kn 个点，
     * 对于每个点都被插入删除各一次，故总的时间代价即渐进时间复杂度为 O(kn×logk)。
     * 空间复杂度：这里用了优先队列，优先队列中的元素不超过 k 个，故渐进空间复杂度为 O(k)。
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        // 处理边界情况 lists = []
        if (lists == null) return null;
        // 创建优先级队列并指定升序比较器
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new compare());
        // 将每个链表的头节点加入优先级队列
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null){
                queue.add(lists[i]);
            }
        }
        // 处理边界情况 lists = [[]]
        if (queue.isEmpty()){
            return null;
        }
        // 获取最后链表的头节点
        ListNode head = queue.poll();
        // 将选中获取头节点的下一个节点加入优先级队列
        ListNode pre = head;
        if (pre.next != null) {
            queue.add(pre.next);
        }
        // 依次替换 获取当前队列中最小节点连接到head后，并将这个节点的下一个加入队列
        while (!queue.isEmpty()) {
            ListNode cur = queue.poll();
            pre.next = cur;
            pre = cur;
            if (cur.next != null) {
                queue.add(cur.next);
            }
        }
        return head;

    }
    public class compare implements Comparator<ListNode>{
        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }
    }

解题方法二

/**
     * 顺序合并
     * 用一个变量 ans 来维护以及合并的链表，第 i 次循环把第 i 个链表和 ans 合并，答案保存到 ans 中。
     * 时间复杂度：渐进时间复杂度为OO(k^2 n)。
     * 空间复杂度：没有用到与 k 和 n 规模相关的辅助空间，故渐进空间复杂度为 O(1)。
     * @param lists
     * @return
     */
    public ListNode mergeKLists3(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0; i < lists.length; ++i) {
            ans = mergeTwoLists2(ans, lists[i]);
        }
        return ans;
    }
    public ListNode mergeTwoLists2(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }

解题方法三

/**
     * 分治合并
     * 时间复杂度：渐进时间复杂度为O(kn×logk)。
     * 空间复杂度：递归会使用到O(logk) 空间代价的栈空间。
     * @param lists
     * @return
     */
    public ListNode mergeKLists2(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }
    public ListNode merge(ListNode[] lists, int l, int r) {
        // 同一个list 直接返回
        if (l == r) {
            return lists[l];
        }
        // 越界 直接返回
        if (l > r) {
            return null;
        }
        // 求中点 进行二分
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }
    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        // 如果有一个链表为null 则返回另一个
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        // 以下进行两个有序链表的合并 并返回
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }

微信关注

WeChat