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