链表中进行排序的归并算法
链表排序的核心就是断链+合并链表
主要涉及到的操作是统计链表长度(来判断最大的合并步长) 分割链表 将两个链表进行合并
/*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) {}
};*/
ListNode* sortList(ListNode* head) {
/* 此为归并算法进行求解
if(!head) return nullptr; //此判断仅用来排除[]测试点
//尝试采用递归的归并排序进行解题
//使用快慢指针找到中间结点
ListNode *p,*q;
p=head;
q=head->next;
if(!q) return p; //只有一个结点
while(q && q->next){
p=p->next;
q=q->next->next;
}
//将链表断开
q=p->next;
p->next=nullptr;
head=sortList(head);
q=sortList(q);
return Merge(head,q);
*/
//使用迭代归并进行排序
ListNode *_head=new ListNode;
_head->next=head;
int count=count_len(head);
ListNode *cur,*pre;
for(int i=1;i<count;i*=2){
pre=_head; cur=_head->next; //进行初始化
while(cur!=nullptr){
ListNode *h1=cur;
ListNode *h2=cut_list(h1,i);
cur=cut_list(h2,i);
h1=Merge(h1,h2);
pre->next=h1;
while(pre->next){
pre=pre->next;
}
}
//print(_head->next);
}
return _head->next;
}
//测试打印输出
/*void print(ListNode *head){
while(head){
cout<<head->val<<" ";
head=head->next;
}
cout<<endl;
}*/
//分割链表
ListNode* cut_list(ListNode *head,int step){
if(!head) return nullptr;
ListNode *p,*q;
p=head;
for(int i=1;i<step && p->next!=nullptr;i++){ //此处应该当心最后剩下的链表不足分割 使用p->next判断的优点是即使不足分割 其代码形式和能够完整分割相同
p=p->next;
}
q=p->next;
p->next=nullptr;
return q;
}
//获取链表的长度
int count_len(ListNode *head){
int count=0;
while(head){
head=head->next;
count++;
}
return count;
}
//将两个链表进行归并
ListNode* Merge(ListNode *head,ListNode *q){
ListNode *_head=new ListNode;
ListNode *p1,*p2,*tem;
p1=head; p2=q; tem=_head;
while(p1 && p2){
if(p1->val <= p2->val){
tem->next=p1;
p1=p1->next;
}
else{
tem->next=p2;
p2=p2->next;
}
tem=tem->next;
}
if(p1) tem->next=p1;
else tem->next=p2;
return _head->next;
}
}
还没有评论,来说两句吧...