伪代码：

• 将链表拆分成两半，返回右半边头节点（左半边头节点就是原始链表头节点）
• 对左边进行排序并返回左边头节点
• 对右边进行排序返回右边头节点
• 传入左右半边头节点，合并两个升序链表

// bug1: 把 cur_a->val <= cur_b->val 写成 cur_a <= cur_b
// 优化1：使用快慢指针找到中间节点，而不是两次遍历//  分治的思想: 链表排序 = 断开左右半部分连接，对左半部分进行排序 + 对右半部分进行排序 + 合并两个升序链表
//  返回 升序链表的头节点
class Solution {
public:// 返回中间节点并拆分链表ListNode* splitList(ListNode* head) {if (head == nullptr || head->next == nullptr) return nullptr;ListNode* slow = head;ListNode* fast = head;ListNode* prev = nullptr;while (fast && fast->next) {prev = slow;slow = slow->next;fast = fast->next->next;}if (prev) prev->next = nullptr; // 拆分链表return slow;}// 合并两个升序链表 (不使用 dummy_head)ListNode* mergeList(ListNode* head_a, ListNode* head_b) {if (!head_a) return head_b;if (!head_b) return head_a;ListNode* merged_head = nullptr;  // 合并后链表的头节点ListNode* cur = nullptr;          // 当前操作的节点// 初始化 merged_head 和 curif (head_a->val <= head_b->val) {merged_head = head_a;head_a = head_a->next;} else {merged_head = head_b;head_b = head_b->next;}cur = merged_head;// 合并剩余节点while (head_a && head_b) {if (head_a->val <= head_b->val) {cur->next = head_a;head_a = head_a->next;} else {cur->next = head_b;head_b = head_b->next;}cur = cur->next;}cur->next = (head_a != nullptr) ? head_a : head_b; return merged_head;}// 归并排序ListNode* sortList(ListNode* head) {if (head == nullptr || head->next == nullptr) return head;// 拆分链表ListNode* mid = splitList(head);// 递归排序前半部分和后半部分ListNode* left = sortList(head);ListNode* right = sortList(mid);// 合并排序后的两个链表return mergeList(left, right);}
};