力扣刷题Day 35：排序链表（148）

1.题目描述

2.思路

递归归并，参考了Krahets佬的解答一：归并排序（递归法）。

3.代码（Python3）

class Solution:def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:if not head or not head.next:return head# 快慢指针分割链表slow, fast = head, head.nextwhile fast and fast.next:slow, fast = slow.next, fast.next.nextmid = slow.nextslow.next = None# 递归left = self.sortList(head)right = self.sortList(mid)# 归并temp = res = ListNode()while left and right:if left.val <= right.val:temp.next = leftleft = left.nextelse:temp.next = rightright = right.nexttemp = temp.nexttemp.next = left if left else rightreturn res.next

4.执行情况

5.感想

这道题给我的感觉是：看起来容易做起来难，不知道为什么。

我的基本功还是太差了，需要好好复习一下排序算法。