给你链表的头结点 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 = [] 输出：[]
归并排序
思路
题目要求O(nlogn)时间复杂度和O(1)空间复杂度，使用归并排序而非是快速排序，归并排序比快排稳定。把链表分割成节点，再合并
代码
class Solution {
public:
ListNode* merge(ListNode* list1, ListNode* list2)
{
ListNode* mergelist = new ListNode(0);
ListNode* node = mergelist;
while(list1 != nullptr && list2 != nullptr)
{
if(list1->val > list2->val)
{
node->next = list2;
list2 = list2->next;
}
else
{
node->next = list1;
list1 = list1->next;
}
node = node->next;
}
if(list1 != nullptr)
node->next = list1;
else if(list2 != nullptr)
node->next = list2;
return mergelist->next;
}
ListNode* sortList(ListNode* head) {
if(head == nullptr || head->next == nullptr)
return head;
int listlen = 0;
ListNode* res = new ListNode(0, head);
while(head != nullptr)
{
head = head->next;
++listlen;
}
for(int i=1; i<listlen; i*=2)
{
ListNode* tmp = res->next;
ListNode* tail = res;
while(tmp != nullptr)
{
ListNode* left = tmp;
for(int j=1; j<i && tmp->next!=nullptr; ++j)
tmp = tmp->next;
ListNode* right = tmp->next;
tmp->next = nullptr;
tmp = right;
for(int j=1; j<i && tmp!=nullptr && tmp->next!=nullptr; ++j)
tmp = tmp->next;
ListNode* next = nullptr;
if(tmp != nullptr)
{
next = tmp->next;
tmp->next = nullptr;
}
tail->next = merge(left, right);
while(tail->next != nullptr)
tail = tail->next;
tmp = next;
}
}
ListNode* secondhead = res->next;
delete res;
return secondhead;
}
};