侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【遍历, 优先队列】合并K个升序链表

GabrielxD
2022-05-25 / 0 评论 / 0 点赞 / 182 阅读 / 652 字
温馨提示:
本文最后更新于 2022-09-21,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

23. 合并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

解题

方法一:遍历

思路

【链表, 双指针】合并两个有序链表 思路差不多,只不过两个链表换成了 K 个链表。

代码

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        ListNode dummy = new ListNode(), prev = dummy;
        while (true) {
            int minIdx = 0, minVal = Integer.MAX_VALUE;
            boolean hasMin = false;
            for (int i = 0; i < len; i++) {
                ListNode curr = lists[i];
                if (curr == null) continue;
                if (curr.val < minVal) {
                    hasMin = true;
                    minIdx = i;
                    minVal = curr.val;
                }
            }
            if (!hasMin) break;
            prev.next = new ListNode(minVal);
            prev = prev.next;
            lists[minIdx] = lists[minIdx].next;
        }
        return dummy.next;
    }
}

方法二:优先队列(小根堆)

思路

维护一个存储节点优先队列,按照节点值的大小升序。把数组中所有不为空的节点入队。创建一个哨兵节点(dummy)与一个遍历节点(prev)用于在其后面连接几点,当队列不为空时每次取一个队头元素(值最小)出来接在遍历节点的后面,遍历节点向后推,如果该队头节点的后继节点不为空时,把该节点入队。最后返回哨兵节点的后继节点即可。

代码

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        Queue<ListNode> minHeap = new PriorityQueue<ListNode>((a, b) -> a.val - b.val);
        for (ListNode list : lists) {
            if (list != null) minHeap.offer(list);
        }
        ListNode dummy = new ListNode(), curr = dummy;
        while (!minHeap.isEmpty()) {
            ListNode minNode = minHeap.poll();
            curr.next = minNode;
            curr = curr.next;
            if (minNode.next != null) minHeap.offer(minNode.next);
        }
        return dummy.next;
    }
}
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> min_heap(cmp);
        for (auto list : lists) {
            if (list) min_heap.push(list);
        }
        ListNode* dummy = new ListNode(), * curr = dummy;
        while (!min_heap.empty()) {
            ListNode* min_node = min_heap.top();
            min_heap.pop();
            curr->next = min_node;
            curr = curr->next;
            if (min_node->next) min_heap.push(min_node->next);
        }
        return dummy->next;
    }
};
0

评论区