前往此题

解题思路 — 归并排序

通过递归的方式来实现对链表的归并排序，分为以下几个步骤

1. 对链表进行分割，按照中间位节点将链表分割成左右两部分
   1. 通过双指针slow、fast找到中点，然后将slow的下一个节点设为None来切割链表
   2. 进入递归继续分割，直到head.next == None
2. 对所有节点依次排序后合并：
   1. 同样需要双指针来辅助，现在我们已经将链表分割成了N个两部分left、right
   2. left与right分别指向各链表的头部，同时创建辅助链表h作为结果，并将res作为它的头部标记
   3. 比较left与right节点大小，有小到大合并到h中
   4. 最后返回h链表的头部res.next

代码

# 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: ListNode) -> ListNode:
        if not head or not head.next: return head
        slow, fast = head, head.next

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        mid = slow.next
        slow.next = None

        left = self.sortList(head)
        right = self.sortList(mid)

        h = res = ListNode(0)
        while left and right:
            if left.val < right.val: h.next, left = left, left.next
            else: h.next, right = right, right.next
            h = h.next
        h.next = left if left else right
        return res.next