LeetCode 23 合并 K 个升序链表

题目描述

合并 K 个升序链表

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

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

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

解法

1. 暴力解法

依次从K个链表的头节点开始遍历，取节点值最小的，然后移动到下一个节点，其他节点不变，继续遍历

java代码：

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 哑结点
        ListNode dummy = new ListNode(0, null);
        ListNode currNode = dummy;
        // 已遍历完的链表的数量
        int noneCount = 0;

        // 存储目前所有节点的值
        int[] valList = new int[lists.length];
        for (int i = 0; i < lists.length; i++) {
            ListNode node = lists[i];
            if (node != null) {
                valList[i] = node.val;
            } else {
                valList[i] = Integer.MAX_VALUE;
                noneCount ++;
            }
        }
        while (noneCount < lists.length) {
            int minIndex = findMinIndex(valList);
            ListNode node = lists[minIndex];
            // 更新结果节点
            currNode.next = node;
            currNode = currNode.next;

            // 如果下一个节点不是null，则更新到当前最小值节点的下一个节点，并更新值是为下一个节点的值
            if (node.next != null) {
                lists[minIndex] = node.next;
                valList[minIndex] = node.next.val;
            } else {
                // 如果下一个节点是null，则更新下一个节点为null，并更新值是为Integer.MAX_VALUE
                lists[minIndex] = null;
                valList[minIndex] = Integer.MAX_VALUE;
                noneCount ++;
            }
        }
        return dummy.next;
    }

    /**
     * 找数组中最小值的索引
     *
     * @param valList
     * @return
     */
    private int findMinIndex(int[] valList) {
        int min = 0;
        for (int i = 0; i < valList.length; i++) {
            if (valList[min] > valList[i]) {
                min = i;
            }
        }
        return min;
    }
}

2. 优先队列

在优先队列里维护当前每个链表没有被合并的元素的最前面一个

class Solution {
    class Status implements Comparable<Status> {
        int val;
        ListNode ptr;

        Status(int val, ListNode ptr) {
            this.val = val;
            this.ptr = ptr;
        }

        @Override
        public int compareTo(Status status2) {
            return this.val - status2.val;
        }
    }

    PriorityQueue<Status> queue = new PriorityQueue<>();

    /**
     * 思路：使用优先队列，在优先队列里维护当前每个链表没有被合并的元素的最前面一个
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        // 初始化优先队列
        for (ListNode node : lists) {
            if (node != null) {
                queue.offer(new Status(node.val, node));
            }
        }

        // 哑结点
        ListNode dummy = new ListNode(0);
        ListNode currNode = dummy;
        while (!queue.isEmpty()) {
            // 拿到队列中的最小节点
            Status status = queue.poll();
            currNode.next = status.ptr;
            currNode = currNode.next;
            // 如果下个节点不为null，继续加到队列
            if (status.ptr.next != null) {
                queue.offer(new Status(status.ptr.next.val, status.ptr.next));
            }
        }
        return dummy.next;
    }
}

复杂度

• 时间复杂度：O(kn×logk)，优先队列中的元素不超过 k 个，那么插入和删除的时间代价为 O(log?k)，这里最多有 kn 个点，对于每个点都被插入删除各一次
• 空间复杂度：O(k),这里用了优先队列，优先队列中的元素不超过 k 个