給你鏈表的頭結(jié)點?head?，請將其按 升序 排列并返回 排序后的鏈表 。示例 1：輸入：head = [4,2,1,3] 輸出：[1,2,3,4] 示例 2：輸入：head = [-1,5,3,4,0] 輸出：[-1,0,3,4,5] 示例 3：輸入：head = [] 輸出：[]

思路:

分割、排序環(huán)節(jié):首先找到當前鏈表中點，并從中點將鏈表斷開，以便在下次遞歸分割排序 時，鏈表片段擁有正確邊界:

我們使用 fast,slow 快慢雙指針法，奇數(shù)個節(jié)點找到中點，偶數(shù)個節(jié)點找到中心左邊的節(jié)點。 找到中點 slow 后，執(zhí)行 slow.next = None 將鏈表切斷。

遞歸分割時，輸入當前鏈表左端點 head 和中心節(jié)點 slow 的下一個節(jié)點 mid(因為鏈表是 從 slow 切斷的)。

遞歸終止條件:當 head.next == None 時，說明只有一個節(jié)點了，直接返回此節(jié)點。

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution:def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:if head == None:return Noneif head.next == None:return head# 雙指針尋找鏈表中點slow = headfast = headwhile fast.next != None and fast.next.next != None:slow = slow.nextfast = fast.next.next# 中點處切斷，得到兩個鏈表mid = slow.nextslow.next = None# 遞歸l1 = self.sortList(head)l2 = self.sortList(mid)return self.merge(l1, l2)def merge(self, l1, l2):dummpy = ListNode(0)cur = dummpywhile l1 != None or l2 != None:if l1 == None:cur.next = l2breakif l2 == None:cur.next = l1breakif l1.val >= l2.val:cur.next = ListNode(l2.val)cur = cur.nextl2 = l2.nextelse:cur.next = ListNode(l1.val)cur = cur.nextl1 = l1.nextreturn dummpy.next

?

總結(jié)

以上是生活随笔為你收集整理的83. Leetcode 148. 排序链表 (排序)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。