代码练习12-排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

归并排序算法核心步骤

归并排序核心步骤如下：

• 把长度为n的要排序的序列，分成两个长度为n/2的子序列；
• 对这两个子序列，分别采用归并排序；
• 将两个排序好的子序列，合并成一个最终有序的排序序列。

对于链表来说，不同于一般的数据序列，它找到中间节点之后，需要切断一下。因此用归并排序算法，去排链表的操作大概是这样：

• 遍历链表，找到中间节点。
• 找到中间节点后，切断
• 分别再用归并排序，排左右子链表
• 合并子链表

 C++核心代码

class Solution {
public:ListNode* sortList(ListNode* head) {if (!head || !head->next) return head;// 获取链表的中间节点ListNode* middle = getMiddle(head);//归并排序：分成两部分//前半部分链表以 head 为起点，到 middle 为终点，后半部分链表以 nextOfMiddle 为起点。ListNode* nextOfMiddle = middle->next;middle->next = nullptr;// 递归排序链表的左右两部分ListNode* left = sortList(head);ListNode* right = sortList(nextOfMiddle);// 合并排序后的链表return merge(left, right);}private:// 合并两个已排序的链表ListNode* merge(ListNode* l1, ListNode* l2) {ListNode dummy(0);ListNode* tail = &dummy;while (l1 && l2) {if (l1->val < l2->val) {tail->next = l1;l1 = l1->next;} else {tail->next = l2;l2 = l2->next;}tail = tail->next;}tail->next = l1 ? l1 : l2;return dummy.next;}// 获取链表的中间节点ListNode* getMiddle(ListNode* head) {if (!head) return head;ListNode* slow = head;ListNode* fast = head->next;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}return slow;}
};