合并 K 个升序链表

Merge k Sorted Lists

问题：合并 K 个升序链表

考察：链表、分治、堆/优先队列

来源：DSA Prep / Citadel

链接：https://leetcode.com/problems/merge-k-sorted-lists

Problem: Merge k Sorted Lists

Patterns: Linked List, Divide and Conquer, Heap (Priority Queue)

Recency: 2yr

Link: https://leetcode.com/problems/merge-k-sorted-lists

Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/

解析

思路：把每个链表头放入按节点值排序的小根堆，每次弹出最小节点接到结果链表，并把它的下一个节点入堆。

复杂度：设总节点数 N，链表数 k，时间 O(N log k)，空间 O(k)。