C++标准归并排序，极致内存操作保证空间复杂度O(1)

class Solution {
public:
    ListNode* slow = nullptr, * fast = nullptr, * head = nullptr, * cur=nullptr;
    ListNode* sortList(ListNode* head) {
        if (!head) return nullptr;
        return MergeSort(head, GetMidNode(head, nullptr), nullptr);
    }
    ListNode* GetMidNode(ListNode* begin, ListNode* end)
    {
        slow = begin; fast = begin;
        while (fast!=end && fast->next!=end)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    ListNode* MergeSort(ListNode* begin, ListNode* mid, ListNode* end)
    {
        if (begin->next == end)
        {
            begin->next = nullptr;
            return begin;
        }
        return Merge(MergeSort(begin, GetMidNode(begin, mid), mid), MergeSort(mid, GetMidNode(mid, end), end));
    }
    ListNode* Merge(ListNode* left, ListNode* right)
    {
        if (left->val < right->val)
        {
            head = left;
            left = left->next;
        }
        else
        {
            head = right;
            right = right->next;
        }
        cur = head;
        while (left && right)
        {
            if (left->val < right->val)
            {
                cur->next = left;
                left = left->next;
                cur = cur->next;
            }
            else
            {
                cur->next = right;
                right = right->next;
                cur = cur->next;
            }
        }
        if (left)
        {
            cur->next = left;
        }
        if (right)
        {
            cur->next = right;
        }
        return head;
    }
};