leetcode 148 排序链表 归并终极形态

还是熟悉的排序，只是换成了链表。要求O(NlogN)复杂度，我们采用归并排序来解决问题，保证每个子问题都是对应的线性复杂度。
技巧1：每次处理子问题，遍历只有一遍，不能遍历子问题数目 * n遍，否则会超时
技巧2：断链：和普通排序不同的是，由于指针随时在移动，不断链很容易出现死循环，以及无法处理的情况，因此我们要断链后，再进行子问题排序。
技巧3：细节，剩余的就是细节了，实在是太难处理，二刷再来研究吧。

/** * 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) {} * }; */classSolution{public:ListNode*sortList(ListNode*head){ListNode*dummy=newListNode(),*last=dummy,*tmp=head;dummy->next=head;intn=0;while(tmp){n++;tmp=tmp->next;}for(intstep=1;step<n;step*=2){ListNode*l=dummy->next;last=dummy;for(intj=0;j<n;j+=step*2){// mid 是第二段开始位置ListNode*mid;tmp=l;for(inti=0;i<step-1;i++){if(tmp)tmp=tmp->next;elsebreak;}if(!tmp||!tmp->next)break;mid=tmp->next;tmp->next=nullptr;tmp=mid;// printf("mid=%d\n", mid->val);// tailfor(inti=0;i<step-1;i++){if(tmp->next)tmp=tmp->next;elsebreak;}ListNode*nxt=nullptr;if(tmp->next)nxt=tmp->next;tmp->next=nullptr;// printf("tail=%d\n", tmp->val);// 排序while(l&&mid){if(l->val<=mid->val)last->next=l,l=l->next;elselast->next=mid,mid=mid->next;last=last->next;}while(l){last->next=l,l=l->next;last=last->next;}while(mid){last->next=mid,mid=mid->next;last=last->next;}last->next=nxt;// l和lastl=nxt;}//tmp=dummy->next;// while(tmp)printf("%d ", tmp->val), tmp = tmp->next;// printf("\n");}returndummy->next;}};