大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
链表排序
链表排序的两种方式
一、交换结点的数据域
有很多种方法，比如冒泡排序，选择排序等其他排序方法
struct Node *link_sort(struct Node *head)
{
int value;
struct Node *p = head;
struct Node *q = NULL;
while(p)
{
q = p->next;
while(q)
{
if(p->data > q->data)
{
value = p->data;
p->data = q->data;
q->data = value;
}
q = q->next;
}
p = p->next;
}
return head;
}
二、断开链表，重新形成
方法
跟三指针法反转链表类似，也是要定义三个结构体指针。
第一步：
第一个指针用于找最小值
第二个指针用于指向最小值的前一个结点
第三个指针用于遍历链表
第二步：
让最小值从链表当中脱离出来
第三步：
然后再定义一个新的指针，用头插法把指向最小值的指针
形成新的链表，通过调整新链表结点的插入方法和在原链表找最值得到升序或降序的效果。
示例
struct Node *link_sort(struct Node *head)
{
struct Node *p = NULL;
struct Node *pMin = NULL;
struct Node *pMin_prev = NULL;
struct Node *newHead = NULL;
while(head)
{
//找到一个最值结点后，重新操作，原链表的结点个数不断减少
p = head;
pMin = head;
pMin_prev = NULL;
//1、找最值，遍历原链表
while(p->next)
{
if(pMin->data > p->next->data) //结点数据域比较
{
pMin_prev = p; //标记
pMin = p->next;
}
p = p->next;
}
//2、将最值结点脱离出原链表
if(pMin == head) //情况一，刚好最值就是头结点
{
head = head->next; //原链表头节点往后移
pMin->next = NULL; //断开连接，同时防止它乱指
}
else
{
pMin_prev->next = pMin->next;//断开结点
pMin->next = NULL;
}
//3、插法入新链表，两种情况
if(newHead == NULL)
{
newHead = pMin;
}
else
{
//头插法
pMin->next = newHead;
newHead = pMin;
}
}
return newHead;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/183186.html原文链接：https://javaforall.net
