排序链表

描述

给你链表的头结点 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 = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sort-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

这个问题的解决方案是使用归并排序来对链表进行排序。归并排序的基本思想是将一个大问题分成两个小问题，递归地解决这些小问题，然后将它们合并成一个大问题的解决方案。在这个问题中，我们将链表分成两个部分，对每个部分递归地进行排序，然后将它们合并在一起。

在代码中，我们使用快慢指针找到链表的中点。然后，我们将链表分成两个部分，对每个部分递归地进行排序。最后，我们将左半部分和右半部分合并在一起。合并的过程中，我们使用一个虚拟节点来简化代码的实现。

C++代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head; // 如果链表为空或者只有一个节点，则直接返回

        // 使用快慢指针找到链表的中点
        ListNode *slow = head, *fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode* mid = slow->next; // 将链表分成两个部分
        slow->next = nullptr;

        ListNode* left = sortList(head); // 递归地对左半部分进行排序
        ListNode* right = sortList(mid); // 递归地对右半部分进行排序

        // 合并左右两部分
        ListNode *dummy = new ListNode(0);
        ListNode* cur = dummy;
        while (left && right) {
            if (left->val < right->val) {
                cur->next = left;
                left = left->next;
            } else {
                cur->next = right;
                right = right->next;
            }
            cur = cur->next;
        }
        if(left) cur->next = left;
        if(right) cur->next = right;
        return dummy->next;
    }
};