struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution {
public:
//归并排序
ListNode* sortList(ListNode* head) {
if (head == nullptr || head->next == nullptr)
return head;
//快慢指针找到中点
ListNode* fast = head->next, slow = head ,l,r;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
ListNode p = slow->next;
slow->next = nullptr;
l = sortList(head);
r = sortList(p);
//合并
ListNode* res = new ListNode(-1);
ListNode* pp = res;
while (l && r) {
if (l->val < r->val) {
pp->next = l;
l = l->next;
}
else {
pp->next = r;
r = r->next;
}
pp = pp->next;
}
if (l)
pp->next = l;
if(r)
pp->next = r;
return res->next;

}

};```

class Solution {
public:
// 带头结点的链表快速排序
void quickSort(ListNode* &head , ListNode* end) {
if (head == end || head->next == end || head->next->next == end)
return;
// 将小于划分点的值存储在临时链表中
ListNode* tmpHead = new ListNode(-1);
// partition为划分点，p为链表指针，tp为临时链表指针
ListNode* tp = tmpHead ,*partition = head->next , *p = partition;
// 将小于划分点的结点放到临时链表中
while (p->next != end) {
if (p->next->val < partition->val) {
tp->next = p->next;
tp = tp->next;
p->next = p->next->next;
}
else {
p = p->next;
}
}
// 合并临时链表和原链表，将原链表接到临时链表后面即可
tp->next = head->next;
// 将临时链表插回原链表，注意是插回！（不做这一步在对右半部分处理时就断链了）
head->next = tmpHead->next;
//释放临时内存
tmpHead->next = NULL;
delete tmpHead;
tmpHead = NULL;

    quickSort(head,partition);
    quickSort(partition,end);

}

ListNode* sortList(ListNode* head) {
    if (head == NULL || head->next == NULL) return head;
    // 没有条件，创造条件。自己添加头节点，最后返回时去掉即可。
    ListNode* newHead = new ListNode(-1);
    newHead->next = head;
    quickSort(newHead,NULL);
    return newHead->next;
}

};