LeetCode热题100-排序链表

给你链表的头结点head请将其按升序排列并返回排序后的链表。示例 1输入head [4,2,1,3]输出[1,2,3,4]核心思路3 步记住1. 分找中点 切分快慢指针快指针走 2 步慢指针走 1 步快指针到末尾时慢指针就在中点断开链表分成左右两半2. 治递归排序两边递归把左右链表都变成有序链表3. 合合并两个有序链表和有序链表合并题逻辑一样用 ** 虚拟头节点dummy** 轻松合并class Solution: def sortList(self, head: Optional[ListNode]) - Optional[ListNode]: if not head or not head.next: return head mid self.find_mid(head) right_head mid.next mid.next None left self.sortList(head) right self.sortList(right_head) return self.merge(left, right) def find_mid(self, head): slow head fast head.next while fast and fast.next: slow slow.next fast fast.next.next return slow def merge(self, l1, l2): dummy ListNode() cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next cur.next l1 if l1 else l2 return dummy.next