23. Merge k Sorted Lists[H]合并k个排序链表

时间:2022-01-25 19:47:21

题目


Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
 Input:
 [
  1->4->5,
  1->3->4;
  2->6
 ]
 Output:1->1->2->3->4->4->5->6

思路


思路1:堆排序

  • 最小堆
  • 优先队列

    思路2:分冶法

Tips


1. 小顶堆

1.1 维护小顶堆性质
1.2 建小顶堆

2. 优先队列

3. 分冶法

C++

Python

参考

[1] 算法导论 第六章