思路
太他妈难了我草
/**
* Definition for singly-linked list.
* 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) {
int n=0;
for(auto p=head;p;p=p->next)n++;
auto dummy=new ListNode(-1);
dummy->next=head;
for(int i=1;i<n;i*=2)
{
auto cur=dummy;
for(int j=1;j+i<=n;j+=i*2)
{
auto p=cur->next,q=p;
for(int k=0;k<i;k++)q=q->next;
int x=0,y=0;
while(x<i&&y<i&&p&&q)
{
if(p->val<=q->val)cur=cur->next=p,p=p->next,x++;
else cur=cur->next=q,q=q->next,y++;
}
while(x<i&&p)cur=cur->next=p,p=p->next,x++;
while(y<i&&q)cur=cur->next=q,q=q->next,y++;
cur->next=q;//将cur->next移向新的j循环开始节点,不然的话cur->next只可能指在p段或q段上,不可能指向q段的下一个节点。
}
}
return dummy->next;
}
};