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

题目

---

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] 算法导论 第六章