C++实现单链表按k值重新排序的方法
时间：2021-04-11 08:55:48|栏目：C代码|点击： 次
本文实例讲述了C++实现单链表按k值重新排序的方法。分享给大家供大家参考，具体如下：
题目要求：
给定一链表头节点，节点值类型是整型。
现给一整数k，根据k将链表排序为小于k，等于k，大于k的一个链表。
对某部分内的节点顺序不做要求。
算法思路分析及代码(C)
思路：将链表分为小于k、等于k、大于k的三个链表，然后再合并。
链表结点定义：
typedef struct Node
{
int data;
struct Node* next;
}node, *pNode;
算法代码：
pNode sortLinkedList(pNode head, int k)
{
pNode sHead = NULL;//小头
pNode sTail = NULL;//小尾
pNode eHead = NULL;//等头
pNode eTail = NULL;//等尾
pNode bHead = NULL;//大头
pNode bTail = NULL;//大尾
pNode temp = NULL;
//拆分链表
while (head != NULL)
{
temp = head->next;
head->next = NULL;
if (head->data < k)
{
if (!sHead){
sHead = head;
sTail = head;
}
else{
sTail->next = head;
sTail = head;
}
}
else if (head->data == k)
{
if (!eHead){
eHead = head;
eTail = head;
}
else{
eTail->next = head;
eTail = head;
}
}
else
{
if (!bHead){
bHead = head;
bTail = head;
}
else{
bTail->next = head;
bTail = head;
}
}
head = temp;
}
//合并链表
if (sTail)
{
sTail->next = eHead;
eTail = (eTail == NULL ? sTail : eTail);
}
if (eTail)
{
eTail->next = bHead;
}
return sHead != NULL ? sHead : (eHead != NULL ? eHead : bHead);
}
希望本文所述对大家C++程序设计有所帮助。
