合并

k

個排序鏈表，返回合并后的排序鏈表。請分析和描述算法的復雜度。

示例:

輸入:[

1->4->5,

1->3->4,

2->6

]輸出:?1->1->2->3->4->4->5->6

#?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?

res?=?left

res.next?=?self.merge(left.next,?right)????????else:

res?=?right

res.next?=?self.merge(left,?right.next)????????return?res

總結

以上是生活随笔為你收集整理的python排序链表_合并K个排序链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。