本文实例讲述了C++实现单链表按k值重新排序的方法。分享给大家供大家参考，具体如下：
题目要求：
给定一链表头节点，节点值类型是整型。
现给一整数k，根据k将链表排序为小于k，等于k，大于k的一个链表。
对某部分内的节点顺序不做要求。
算法思路分析及代码(C)
思路：将链表分为小于k、等于k、大于k的三个链表，然后再合并。
链表结点定义：
?
|
1
2
3
4
5
|
typedef struct Node
{
int data;
struct Node* next;
}node, *pNode;
|
算法代码：
?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
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);
}
|
