题解 | #单链表的排序#

归并排序的样板代码，主要是合并两个链表的部分，以及要注意在归并前需要断开链表，否则会死循环。

#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

class Solution {
public:
    ListNode* mergeSort(ListNode* head) {
        if(head==NULL || head->next==NULL)
            return head;
        ListNode *fast = head, *slow = head, *pre;
        while(fast && fast->next) {
            pre = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        pre->next = NULL;
        ListNode* left = mergeSort(head);
        ListNode* right = mergeSort(slow);
        ListNode* dummy = new ListNode(0);
        ListNode* p = dummy;
        while(left || right) {
            if(left == NULL || (right && right->val < left->val)) {
                p->next = right;
                right = right->next;
            }
            else{
                p->next = left;
                left = left->next;
            }
            p = p->next;
        }
        return dummy->next;
    }
    ListNode* sortInList(ListNode* head) {
        return mergeSort(head);
    }
};