- 难度: 困难
- 考察: 链表
- 来源: https://leetcode-cn.com/problems/merge-k-sorted-lists/
- 题解: https://github.com/MisterBooo/LeetCodeAnimation/blob/master/0023-Merge-k-Sorted-Lists/Article/0023-Merge-k-Sorted-Lists.md
- 题解: https://github.com/azl397985856/leetcode/blob/master/problems/23.merge-k-sorted-lists.md
- 题解: https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/he-bing-kge-pai-xu-lian-biao-by-leetcode-solutio-2/
题目
合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
1 | 输入: |
思路
暴力合并
- 循环k个链表,找到最小数m,将m从原链表移动到结果列表ans
- 循环步骤1,直到k个链表的元素全部移动到ans
顺序合并
k个链表依次合并到结果链表ans
分治合并
- k个链表两两合并
- 合并的结果继续两两合并,直到只剩一个结果链表ans
关键点
- 有序链表
复杂度
- 时间复杂度:O(K*N)
- 空间复杂度:O(1)
代码
暴力合并
1 | /** |