当前位置 博文首页 > Scissors_初夏的博客:初夏小谈:分割链表(链表进阶操作)
分割链表:
在单链表中取任意一个结点的数据,然后对链表进行排列,比它小的排在它前面,大于等于它的排在它后面,要求保持原相对顺序不变。
先不看这个操作链表,看到这种做法我就想起了一种排序的做法,不知道大家想起了没有。那就是快速排序思想。在后面的文章中我会尽力去挖掘快排,为大家展现快排的魅力。
因为任意取结点中的数据作为参考值,所以就可以把源结点分为两部分即:比参考结点的数据小的在一起,其它的放在一起。这样分类后,就可能存在小的没有,或大于等于的也没有。对特殊情况也要充分考虑。
因此就可以定义两个头指针经过一系列的尾插过程,最后再把两个链表连接起来。
代码实现:
void MidOrdered(LinkList* first, DataType data)
{
assert(first);
if (first->head == NULL)
{
return;
}
LinkList* LTPtr = (LinkList*)malloc(sizeof(LinkList));
InitLinkList(LTPtr);
LinkListNode* LTRailPtr = NULL;
LinkList* ETGTPtr = (LinkList*)malloc(sizeof(LinkList));
InitLinkList(ETGTPtr);
LinkListNode* ETGTRailPtr = NULL;
LinkListNode* ptr = first->head;
while (ptr != NULL)
{
if (ptr->data < data)
{
if (LTPtr->head == NULL)
{
LTPtr->head = ptr;
LTRailPtr = ptr;
ptr = ptr->next;
LTRailPtr->next = NULL;
}
else
{
LTRailPtr->next = ptr;
ptr = ptr->next;
LTRailPtr = LTRailPtr->next;//把最后一个指针往后移
LTRailPtr->next = NULL;
}
}
else
{
if (ETGTPtr->head == NULL)
{
ETGTPtr->head = ptr;
ETGTRailPtr = ptr;
ptr = ptr->next;
ETGTRailPtr->next = NULL;
}
else
{
ETGTRailPtr->next = ptr;
ptr = ptr->next;
ETGTRailPtr = ETGTRailPtr->next;
ETGTRailPtr->next = NULL;
}
}
}
if (LTPtr->head == NULL)
{
first->head = ETGTPtr->head;
}
else if (LTPtr->head != NULL && ETGTPtr->head == NULL)
{
first->head = LTPtr->head;
}
else
{
LTRailPtr->next = ETGTPtr->head;
first->head = LTPtr->head;
}
}
cs在开始操作链表前一定要对指针进行初始化。指针就像一条没栓链子的狗狗一样,它可能做出一些不可思议的操作,所以就要初始化就如同给狗狗拴上链子一样。完成分割合并中,一定注意及时更新指针。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?珍&源码