力扣hot100——排序链表（常见方法，归并排序）

解题思路：

1. 分解（Divide）：将待排序的列表递归地分成两半，直到每个子列表只包含一个元素（此时每个子列表都是有序的）。
2. 解决（Conquer）：递归地对每个子列表进行排序。由于每个子列表在分解过程中最终只包含一个元素，因此它们自然是有序的。排序的过程实际上是合并的过程。
3. 合并（Combine）：将两个有序的子列表合并成一个有序的列表。

步骤

1. 递归分解：
   • 如果列表的长度为1或0，则直接返回该列表（因为它已经是有序的）。
   • 否则，找到列表的中间位置，将列表分成两个子列表。
   • 递归地对两个子列表进行归并排序。
2. 合并：
   • 创建一个新的空列表用于存放合并后的结果。
   • 使用两个指针分别指向两个子列表的开头。
   • 比较两个指针所指向的元素，将较小的元素添加到新列表中，并将相应指针向前移动一位。
   • 重复上述步骤，直到其中一个子列表中的所有元素都添加到新列表中。
   • 将另一个子列表中剩余的元素（如果有）添加到新列表中。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* sortList(ListNode* head) {if (!head || !(head->next)) {return head;}// 归并排序：首先一分为二ListNode *slow = head;ListNode *fast = head->next;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}ListNode *second = slow->next;slow->next = NULL;ListNode *first = head;// 递归进行归并排序first = sortList(first);second = sortList(second);return Merge(first,second); // 合并后链表}ListNode* Merge(ListNode*first,ListNode*second){ListNode* dummy = new ListNode(0);ListNode* tail = dummy;while(first && second){if(first->val > second->val){tail->next = second;second = second->next;}else{tail->next = first;first = first->next;}tail = tail->next;}// 存在没有加入的部分则加入dummyif(first){tail->next = first;}else if(second){tail->next = second;}return dummy->next;}};