题目描述：来自LeetCode?
方法一：自顶向下+递归?
思路：因为要求（NlongN）时间复杂度，可能会想到二分，归并等排序方法，这里对链表的合并，因为不是有序，所以用归并比较合适。
空间复杂度O(logn)，其中?n 是链表的长度。空间复杂度主要取决于递归调用的栈空间
找到链表的中间位置（快慢指针）
对左边一般进行排序，对右边一半进行排序
合并两个有序的子链表
代码实现C++:
class Solution {
public:
ListNode* sortList(ListNode* head) {
return sortt(head,NULL);
}
ListNode* sortt(ListNode *head,ListNode *tail){
//递归结束条件就是当链表为空或者只有一个节点了，那就不用排序了
if(head==NULL) return head;
if(head->next==tail) {
head->next=NULL;
return head;
}
//定义快慢指针，慢指针走一步，快指针走两步，当快指针到达链表结尾的时候，慢指针到链表中间结点
ListNode *slow=head,*qui=head;
while(qui!=tail){
slow=slow->next;
qui=qui->next;
if(qui!=tail){
qui=qui->next;
}
}
//对做边的子链表和右边的子链表继续归并
ListNode *mid=slow;
ListNode* be=sortt(head,mid);
ListNode* en=sortt(mid,tail);
/每次归并都将两个子链表合并为一个有序链表
ListNode* result=mergeLink(be,en);
return result;
}
ListNode* mergeLink(ListNode *be,ListNode *en){
ListNode *res=new ListNode();//定义一个头结点用来指向归并后的链表
ListNode *p=res,*p1=be,*p2=en;
while(p1&&p2){
if(p1->val<p2->val){//入p1指向的值比p2小，就用尾插法将p1接在p的后面，p1后移一位
p->next=p1;
p1=p1->next;
}else{
p->next=p2;
p2=p2->next;
}
p=p->next;//p后移一位，因为要保证p指向归并结果链表的尾部
}
//最后有一个链表可能没有遍历结束，因为每次归并子链表已经有序，所以直接将没有遍历完的链表接在尾部
if(!p1) p->next=p2;
else p->next=p1;
return res->next;
}
};?方法二：自底向上
在自顶向上时由于递归的调用空间复杂度不是常数了，如果想让空间复杂度是常数级，就应该修改递归拆分链表的过程，我们自己来拆分，归并的时候，是将数组一分二，二分四...然后回溯不停的二和一来排序，我们直接从分组到最小来开始，就是归并的回溯过程，我们先一个个排序，再每两个进行排序，再每四个进行排序...，直到排序的子表的长度大于等于链表，排序结束。
代码实现C++:
class Solution {
public:
ListNode* sortList(ListNode* head) {
if(head==NULL) return head;
ListNode *p=head;
int length=0;//计算链表长度
while(p){
p=p->next;
length++;
}
//拆分链表，从1开始
ListNode *newLink=new ListNode(0,head);
for(int subLink=1;subLink<length;subLink<<=1){
ListNode *pre=newLink,*cur=newLink->next;//pre用来记录当前已排序的子链表的尾结点，cur用来记录即将要拆分的子链表的起始位置
while(cur){//当cur==NULL说明一趟切分结束，开始下一轮的切分
ListNode *head1=cur;//第一个子链表的头结点指向当前要拆分分起始位置
for(int i=1;i<subLink&&cur->next!=NULL;i++){//循环subLink-1，因为子链表的长度是subLink
cur=cur->next;//最后cur指向第一个子链表的尾部
}
ListNode *head2=cur->next;//第二个子链表的头结点指向第一个子链表的下一个位置
cur->next=NULL;//将第一个子链表从链表中切开
cur=head2;//改变当前位置继续拆分
for(int i=1;i<subLink&&cur!=NULL&&cur->next!=NULL;i++){//循环subLink-1，因为子链表的长度是subLink
cur=cur->next;//最后cur指向第二个子链表的尾部
}
ListNode *next=NULL;//next记录下一次拆分的位置，其实就是本次拆分的第二个链表的尾部的下一个位置
if(cur!=NULL){//如果cur是空，那就不用继续拆分了，如果不是，将改变next
next=cur->next;
cur->next=NULL;//将第二个链表从原链表中切开
}
ListNode* merged=mergeLink(head1,head2);//归并排序两个被拆分出来的链表
pre->next=merged;
while(pre->next){//改变pre的位置，指向当前已排序的链表尾部
pre=pre->next;
}
cur=next;//改变下一次切割的起始位置
}
}
return newLink->next;
}
ListNode* mergeLink(ListNode *be,ListNode *en){
ListNode *res=new ListNode();//定义一个头结点用来指向归并后的链表
ListNode *p=res,*p1=be,*p2=en;
while(p1&&p2){
if(p1->val<p2->val){//入p1指向的值比p2小，就用尾插法将p1接在p的后面，p1后移一位
p->next=p1;
p1=p1->next;
}else{
p->next=p2;
p2=p2->next;
}
p=p->next;//p后移一位，因为要保证p指向归并结果链表的尾部
}
//最后有一个链表可能没有遍历结束，因为每次归并子链表已经有序，所以直接将没有遍历完的链表接在尾部
if(!p1) p->next=p2;
else p->next=p1;
return res->next;
}
};今日刷题任务完成，如有错误，欢迎指正