C 单向链表排序_单向链表排序java

全栈程序员站长

发布于 2022-11-10 15:57:34

6330

发布于 2022-11-10 15:57:34

文章被收录于专栏：全栈程序员必看

链表排序

链表排序的两种方式

链表排序的两种方式

一、交换结点的数据域

有很多种方法，比如冒泡排序，选择排序等其他排序方法

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.cn/183186.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年10月11日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法