题目：

        给你链表的头结点 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 = []
输出：[]

提示：

• 链表中节点的数目在范围 [0, 5 * 104] 内

• -105 <= Node.val <= 105

---

思路如下：

        这道题思想是链表的归并排序算法，主要分为三个部分：middleNode、mergeTwoLists 和 sortList。首先要找到链表的中间节点，将链表分成两部分。其次通过将较小的节点连接到新链表，实现合并链表。最后对合并后的新链表进行归并排序，得到排序后的链表，返回链表头节点。

---

题解如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
​
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 使用快慢指针法找到链表的中间节点
        slow = fast = head
        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next
        pre.next = None
        return slow  # 返回中间节点
​
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # 合并两个有序链表
        p0 = dummy = ListNode(-1)
        while list1 and list2:
            if list1.val < list2.val:
                p0.next = list1  # 将较小的节点连接到结果链表
                list1 = list1.next
            else:
                p0.next = list2  # 将较小的节点连接到结果链表
                list2 = list2.next
            p0 = p0.next  # 移动结果链表的构建指针
        # 处理剩余的节点
        if list1:
            p0.next = list1  # 如果 list1 还有剩余，直接连接
        elif list2:
            p0.next = list2  # 如果 list2 还有剩余，直接连接
        return dummy.next  # 返回合并后的链表头节点
​
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 对链表进行归并排序
        if not head or not head.next:
            return head  # 如果链表为空或只有一个节点，直接返回
        # 使用 middleNode 将链表分成两部分
        head2 = self.middleNode(head)
        # 递归地对两部分进行排序
        head = self.sortList(head)
        head2 = self.sortList(head2)
        # 合并排序后的两部分
        return self.mergeTwoLists(head, head2)

---

题解示例：

​
假设有一个链表：4 → 2 → 1 → 3 → 5 → 6。
最终结果应该是：1 → 2 → 3 → 4 → 5 → 6。
​
1. sortList 函数的初始调用
调用 sortList(head)，链表为 4 → 2 → 1 → 3 → 5 → 6。
​
2. 找到中间节点
调用 middleNode(head)：
使用快慢指针法找到中间节点。
快指针 fast 每次移动两步，慢指针 slow 每次移动一步。
当 fast 到达链表末尾时，slow 指向中间节点 3。
链表被分割为两部分：
第一部分：4 → 2 → 1
第二部分：3 → 5 → 6
​
3. 递归排序第一部分
调用 sortList 对第一部分 4 → 2 → 1 进行排序。
3.1 再次找到中间节点
使用 middleNode 找到中间节点 2。
第一部分被分割为 4 和 2 → 1。
3.2 递归排序子部分
对 4 进行排序（已经是单节点，直接返回）。
对 2 → 1 进行排序：
找到中间节点 2，分割为 2 和 1。
递归排序后，合并为 1 → 2。
3.3 合并子部分
合并 4 和 1 → 2，得到 1 → 2 → 4。
​
4. 递归排序第二部分
调用 sortList 对第二部分 3 → 5 → 6 进行排序。
4.1 再次找到中间节点
使用 middleNode 找到中间节点 5。
第二部分被分割为 3 和 5 → 6。
4.2 递归排序子部分
对 3 进行排序（已经是单节点，直接返回）。
对 5 → 6 进行排序：
找到中间节点 5，分割为 5 和 6。
递归排序后，合并为 5 → 6。
4.3 合并子部分
合并 3 和 5 → 6，得到 3 → 5 → 6。
​
5. 合并两部分
调用 mergeTwoLists 合并 1 → 2 → 4 和 3 → 5 → 6。
5.1 合并过程
比较 1 和 3，选择 1，结果链表为 1。
比较 2 和 3，选择 2，结果链表为 1 → 2。
比较 4 和 3，选择 3，结果链表为 1 → 2 → 3。
比较 4 和 5，选择 4，结果链表为 1 → 2 → 3 → 4。
比较 5 和 6，选择 5，结果链表为 1 → 2 → 3 → 4 → 5。
最后将剩余的 6 连接到结果链表。
​
最终合并后的链表为：1 → 2 → 3 → 4 → 5 → 6。
​

---

逻辑梳理：

1. middleNode 函数

这个函数用于找到链表的中间节点，以便将链表分成两部分。

• 功能：使用快慢指针法找到链表的中间节点。

  • slow 指针每次移动一步，fast 指针每次移动两步。

  • 当 fast 到达链表末尾时，slow 指针正好在中间。

  • `pre.next = None 将链表分成两部分，head 和 slow 分别是两部分的头节点。

• 返回值：返回链表的中间节点。

2. mergeTwoLists 函数

这个函数用于合并两个有序链表。

• 功能：合并两个有序链表。

  • 使用一个虚拟头节点 dummy 来简化链表的构建。

  • 遍历两个链表，每次将较小的节点连接到结果链表中。

  • 如果其中一个链表遍历结束，将剩余的节点直接连接到结果链表。

• 返回值：返回合并后的有序链表的头节点。

1. sortList 函数

这是主函数，用于对链表进行归并排序。

• 功能：对链表进行归并排序。

  • 如果链表为空或只有一个节点，直接返回。

  • 使用 middleNode 将链表分成两部分。

  • 递归地对两部分进行排序。

  • 使用 mergeTwoLists 合并排序后的两部分。

• 返回值：返回排序后的链表头节点。