合并K个排序链表
发布时间：2025-08-31 20:55:42
作者：益华网络
来源：undefined
浏览量（0）
点赞（0）
摘要：合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。 示例:
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:[ 1->4->5, 1->3->4, 2->6 ]输出: 1->1->2->3->4->4->5->61
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Definition for singly-linked list.# class ListNode(object):# def __init__(self, x):# self.val = x# self.next = Noneclass Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
#合成一个大的listlist然后排序
lists = [x for x in lists if x] if not lists or all([not x for x in lists]): return
head = lists.pop()
curr = head while curr.next:
curr = curr.next
while lists:
tmp = lists.pop()
curr.next = tmp while tmp.next:
tmp = tmp.next
curr = tmp
if not head or not head.next: return head return self.mergeSort(head)
def mergeSort(self, head):
if not head.next: return head
pre, slow, fast = None, head, head
while fast and fast.next:
prev, slow, fast = slow, slow.next, fast.next.next
prev.next = None
left = self.mergeSort(head)
right = self.mergeSort(slow) return self.merge(left, right)
def merge(self, left, right):
if not left: return right if not right: return left
if left.val < right.val:
res = left
res.next = self.merge(left.next, right) else:
res = right
res.next = self.merge(left, right.next) return res
扫一扫，关注我们
声明：本文由【益华网络】编辑上传发布，转载此文章须经作者同意，并请附上出处【益华网络】及本页链接。如内容、图片有任何版权问题，请联系我们进行处理。
0
