class ListNode:
def __init__(self, x):
self.val = x
self.next = None
a = ListNode(1)
b = ListNode(3)
c = ListNode(2)
d = ListNode(1)
e = ListNode(5)
a.next = b
b.next = c
c.next = d
d.next = e
# 這道題是用歸并排序的方法
class Solution:
def sortList(self, head: ListNode) -> ListNode:
# 首先判斷鏈表是否只有一個節點，或者鏈表為空
if not head or not head.next:return head
# 定義兩個快慢指標，用來找出鏈表的中間節點，用于等下遞回的出口和入口
slow,fast = head,head.next
# 遍歷鏈表，找出中間那個節點
while fast and fast.next:
slow,fast = slow.next,fast.next.next
# 然后將鏈表分為兩邊，進行遞回歸并排序
slow.next,mid = None,slow.next
left = self.sortList(head)
right = self.sortList(mid)
# 定義一個節點，用來當做重新排序后鏈表的頭結點
node = ListNode(0)
node1 = node
# 遍歷然后用于歸并排序后的合成
while left and right:
if left.val > right.val:
node.next,right = right,right.next
else:
node.next,left = left,left.next
node = node.next
node.next = left if left else right
# 最后回傳這個鏈表，
return node1.next
A = Solution()
print(A.sortList(a))
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/71709.html
標籤：Python
上一篇：三元運算式