一、问题描述
合并 ķ 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1-> 4-> 5,
1-> 3-> 4,
2-> 6
]
输出: 1-> 1-> 2-> 3-> 4-> 4-> 5-> 6
2.算法设计:
方法1:暴力
想法 & 算法
- 遍历所有链表,将所有节点的值放到一个数组中。
- 将这个数组排序,然后遍历所有元素得到正确顺序的值。
- 用遍历得到的值,创建一个新的有序链表。
关于排序,你可以参考 这里 获得更多关于排序算法的内容。
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
self.nodes = []
head = point = ListNode(0)
for l in lists:
while l:
self.nodes.append(l.val)
l = l.next
for x in sorted(self.nodes):
point.next = ListNode(x)
point = point.next
return head.next
复杂度分析
- 时间复杂度:O(NlogN) ,其中 N 是节点的总数目。
- 遍历所有的值需花费 O(N) 的时间。
- 一个稳定的排序算法花费O(NlogN) 的时间。
- 遍历同时创建新的有序链表花费O(N) 的时间。
- 空间复杂度:O(N) 。
- 排序花费 O(N) 空间(这取决于你选择的算法)。
- 创建一个新的链表花费O(N) 的空间。
网友评论