C++ implements the method of reordering single linked list by k value
- 2020-05-19 05:15:02
- OfStack
This article illustrates an example of how C++ can reorder a single linked list by k values. I will share it with you for your reference as follows:
Title requirements:
Given a 1 - chain header node, the node value type is integer.
Now give 1 integer k, and order the list according to k to be less than k, equal to k, and more than one list of k.
The order of nodes in a part is not required.
Algorithm analysis and code (C)
Idea: divide the list into three lists less than k, equal to k, and greater than k, and then merge them.
List node definition:
typedef struct Node
{
int data;
struct Node* next;
}node, *pNode;
Algorithm code:
pNode sortLinkedList(pNode head, int k)
{
pNode sHead = NULL;// Little head
pNode sTail = NULL;// Small tail
pNode eHead = NULL;// Such as the head
pNode eTail = NULL;// Such as the tail
pNode bHead = NULL;// Big head
pNode bTail = NULL;// Leg,
pNode temp = NULL;
// Break up the list
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;
}
// Merge list
if (sTail)
{
sTail->next = eHead;
eTail = (eTail == NULL ? sTail : eTail);
}
if (eTail)
{
eTail->next = bHead;
}
return sHead != NULL ? sHead : (eHead != NULL ? eHead : bHead);
}
I hope this article is helpful to you C++ programming.