struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(NULL) {}
ListNode(int x) : val(x), next(NULL) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
ListNode* sort(ListNode* head) {
if(head==NULL)
return NULL;
ListNode* end=head;
while(end->next)
{
end=end->next;
}
return sortList(head,end);
}
ListNode* sortList(ListNode* head,ListNode* end) {
if(head==end)
return head;
if(head->next==end)
{
int tempp;
if(head->val>head->next->val)
{
tempp=head->val;
head->val=head->next->val;
head->next->val=tempp;
}
return head;
}
ListNode* mid=head,*tail=head->next;
while(tail!=end)
{
mid=mid->next;
tail=tail->next;
if(tail->next)
tail=tail->next;
}
ListNode* midnext=mid->next;//保存第二个链表首地址
mid->next=NULL;//断开两段链表
return mergeList(sortList(head,mid),sortList(midnext,end));
}
ListNode* mergeList(ListNode* a,ListNode* b){
ListNode* tempnode= new ListNode(0);//建立个头节点,方便下面的处理,两链表元素均放在此头结点之后
ListNode* traverse= tempnode;
while(a&&b)//两链表均有元素
{
if(a->val<=b->val)
{
traverse->next=a;
a=a->next;
}else
{
traverse->next=b;
b=b->next;
}
traverse=traverse->next;
}
if(a)
traverse->next=a;
if(b)
traverse->next=b;
return tempnode->next;
}
};
原文链接: https://www.cnblogs.com/lxzbky/p/14015883.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/399957
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!