LeetCode148.排序链表

题目

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

示例

输入：head = [4,2,1,3]
输出：[1,2,3,4]

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

输入：head = []
输出：[]

思路

对于链表排序我们可以使用链表的归并排序（Merge Sort）算法。下面是整体的思路：

1. 归并排序的核心思想：归并排序是一种分治算法，首先将待排序的链表分成两部分，然后分别对这两部分进行排序，最后将排好序的两部分链表合并起来。

2. mergeSort 函数：这个函数是归并排序的入口，负责调用递归排序的函数 mergeSort，并返回排好序的链表。在 mergeSort 中，首先判断链表是否为空或只有一个节点，如果是，则直接返回原链表。然后找到链表的中间节点 mid，将链表分成左右两部分，分别以 head 和 mid->next 开始。然后分别对左右两部分链表调用 mergeSort 递归排序，最终通过 merge 函数将排好序的两部分链表合并。

3. findMid 函数：这个函数用快慢指针的方法找到链表的中间节点，快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末尾时，慢指针指向的节点即为中间节点。

4. merge 函数：这个函数用于合并两个有序链表。创建一个虚拟头节点 dummyHead 和一个指针 cur，遍历两个链表的节点，根据节点值的大小依次连接到 cur->next 上，然后将 cur 移动到下一个节点。最后，将剩余未遍历完的链表连接到 cur->next 上。返回虚拟头节点的下一个节点即为合并后的有序链表。

综上所述，这段代码通过归并排序算法对链表进行排序，利用分治和合并的思想，最终得到一个按升序排列的链表。

Code

class Solution {
public:ListNode* sortList(ListNode* head) {return mergeSort(head);}ListNode* mergeSort(ListNode* head) {if (!head || !head->next) return head;ListNode* mid = findMid(head);ListNode* l1 = head;ListNode* l2 = mid->next;mid->next = nullptr;l1 = mergeSort(l1);l2 = mergeSort(l2);return merge(l1, l2);}ListNode* findMid(ListNode* head) {ListNode *slow = head, *fast = head;while (fast->next && fast->next->next) {slow = slow->next;fast = fast->next->next;}return slow;}ListNode* merge(ListNode* l1, ListNode* l2) {// l1 >= l2长度ListNode* dummyHead = new ListNode();ListNode* cur = dummyHead;while (l1 && l2) {if (l1->val <= l2->val) {cur->next = l1;l1 = l1->next;}else {cur->next = l2;l2 = l2->next;}cur = cur->next;}cur->next = l1 ? l1 : l2;return dummyHead->next;}
};