leetcode148. 排序链表

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

解题思路：
归并排序：找到中间节点，分成两个链表。递归合并
代码如下：

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* pre = new ListNode(0);
        pre->next = slow;
        while (fast != nullptr) {
            slow = slow->next;
            pre = pre->next;
            fast = fast->next;
            if (fast != nullptr) fast = fast->next;
        }
        pre->next = nullptr;
        ListNode* res = mergelist(sortList(head), sortList(slow));
        return res;

    }
    ListNode* mergelist(ListNode* left, ListNode* right) {
        ListNode* head = new ListNode(0);
        ListNode* temp = head;
        while (left != nullptr && right != nullptr) {
            if (left->val < right->val) {
                temp->next = left;
                left = left->next;
            } else {
                temp->next = right;
                right = right->next;
            }
            temp = temp->next;
        }
        if (left != nullptr) temp->next = left;
        else if (right != nullptr) temp->next = right;
        return head->next;
    }
    //归并排序
};