题目
给你链表的头结点 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 = [] 输出：[]
分析
要对单链表进行排序并返回排序后的链表，可使用归并排序算法。
归并排序
代码解释
sortList 函数：
首先检查链表是否为空或只有一个节点，如果是，则直接返回该链表。
调用 getMiddle 函数找到链表的中间节点，将链表从中间断开为左右两部分。
递归地对左右两部分进行排序。
调用 merge 函数将两个有序链表合并成一个有序链表。
getMiddle 函数：
使用快慢指针法找到链表的中间节点。快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末尾时，慢指针刚好指向链表的中间节点。
merge 函数：
创建一个虚拟头节点 dummy，并使用 tail 指针来构建合并后的链表。
比较两个链表的当前节点值，将较小值的节点添加到 tail 后面，并移动相应的指针。
处理剩余的节点，将未遍历完的链表直接连接到 tail 后面。
时间复杂度：O()，
是链表的长度
空间复杂度：O()
class Solution {
public:ListNode* sortList(ListNode* head) {if (head == nullptr || head->next == nullptr) {return head;}// 找到链表的中间节点ListNode* mid = getMiddle(head);ListNode* right = mid->next;mid->next = nullptr; // 断开链表// 递归地对左右两部分进行排序ListNode* leftSorted = sortList(head);ListNode* rightSorted = sortList(right);// 合并两个有序链表return merge(leftSorted, rightSorted);}
private:// 找到链表的中间节点ListNode* getMiddle(ListNode* head) {if (head == nullptr) {return nullptr;}ListNode* slow = head;ListNode* fast = head->next;while (fast != nullptr && fast->next != nullptr) {slow = slow->next;fast = fast->next->next;}return slow;}// 合并两个有序链表ListNode* merge(ListNode* l1, ListNode* l2) {ListNode dummy(0);ListNode* tail = &dummy;while (l1 != nullptr && l2 != nullptr) {if (l1->val < l2->val) {tail->next = l1;l1 = l1->next;} else {tail->next = l2;l2 = l2->next;}tail = tail->next;}if (l1 != nullptr) {tail->next = l1;} else {tail->next = l2;}return dummy.next;}
};