网站管理过程,微信客户联系方式,虚拟主机怎么设计网站,珠海新盈科技有限公司 网站建设链表分割实际上是给定一个值#xff0c;遍历链表把链表中小于该值的节点与大于该值的节点分开#xff0c;一般是将小于该值的节点放到链表的前面部分#xff0c;大于该值的节点放在链表的后面部分。 链表分割示意图如下#xff1a; 思路#xff1a; 首先创建两条带哨兵位节… 链表分割实际上是给定一个值遍历链表把链表中小于该值的节点与大于该值的节点分开一般是将小于该值的节点放到链表的前面部分大于该值的节点放在链表的后面部分。 链表分割示意图如下 思路 首先创建两条带哨兵位节点的新链表并且用big、small指针维护比8大的节点放在big链表比8小的节点放在small链表。 两条新链表则需要创建两个哨兵位。哨兵位节点的作用顾名思义仅仅是起到一个“站岗”的作用也就是把要插入到新链表中的节点直接插到哨兵位节点的后面。 情况一 遍历链表发现比8大的节点将其放到big哨兵位节点的后面如下图: 注意这里不能直接让small和big指针进行遍历因为如果这两个指针往后移动则找不到哨兵位节点的位置了也就找不到链表的初始位置还会面临内存泄漏的风险因为哨兵位是malloc来的没有哨兵位的位置就无法对其进行释放。因此再定义两指针b_travel和s_travel代替移动并且将cur指针移动至下一个节点。
情况二 若发现比8小的节点将其放到small哨兵位节点的后面如下图 同理将cur指针至下一个节点 每次拿下来一个节点都要更新b_travel和s_travel指针指向的位置。如此重复以上操作直到cur指针指向NULL说明链表已遍历结束。
合并链表 接下来是最关键的一步就是将small链表和big链表合二为一最后返回small哨兵位的下一个节点的地址即合并后链表的头节点地址。 切记最后返回的是small哨兵位节点的下一个节点的地址因为small和big开辟的哨兵位节点只是用于“站岗”最后链表链接完成后需要将这两个哨兵位释放。 铺垫了那么久接下来就是代码实现测试代码包括链表的创建、打印以及链表分割功能
#includestdio.h
#includestdlib.htypedef struct ListNode //创建节点结构体
{int data;//存放数据struct ListNode* next;//指向下一个节点
}ListNode;//链表分割函数
ListNode* partition(ListNode* head, int x) {struct ListNode* small NULL;//开始先创建4个指针两两维护链表struct ListNode* big NULL;struct ListNode* s_travel NULL;//这两个指针用于遍历链表struct ListNode* b_travel NULL;//开辟两个哨兵位节点s_travel small (struct ListNode*)malloc(sizeof(struct ListNode));b_travel big (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur head;//用cur指针代替head遍历链表while (cur)//cur为空跳出循环{if (cur-data x)//小于x的节点放到small链表中{s_travel-next cur;s_travel s_travel-next;}else//大于x的节点放到big链表中{b_travel-next cur;b_travel b_travel-next;}cur cur-next;//cur往后走}b_travel-next NULL;//合并链表s_travel-next big-next;struct ListNode* poi small;//记住small哨兵位节点的位置small small-next;//small指向哨兵位后一个节点也就是链表的头节点free(big);//释放哨兵位free(poi);return small;//返回链表头节点位置
}//打印链表函数
void Print(ListNode* phead)
{ListNode* cur phead;while (cur){printf(%d-, cur-data);cur cur-next;}printf(NULL);//模拟链表最后指向的是NULL
}int main()
{ListNode* n1 (ListNode*)malloc(sizeof(ListNode));//创建5个节点为了测试分割链表函数ListNode* n2 (ListNode*)malloc(sizeof(ListNode));ListNode* n3 (ListNode*)malloc(sizeof(ListNode));ListNode* n4 (ListNode*)malloc(sizeof(ListNode));ListNode* n5 (ListNode*)malloc(sizeof(ListNode));ListNode* plist n1;//指向头节点的头指针plistn1-data 12;//给每个节点都赋值n2-data 6;n3-data 23;n4-data 18;n5-data 2;n1-next n2;//手动构建链表n2-next n3;n3-next n4;n4-next n5;n5-next NULL;Print(plist);//打印分割之前的链表ListNode* newhead partition(plist, 8);//分割后返回新的头节点printf(\n分割后:);Print(newhead);//打印分割之后的链表return 0;
} 运行结果 结语 以上就是关于链表分割全部讲解与实现其中对哨兵位节点合理的使用可以很方便解决某些链表问题这种思路在链表问题中尤为重要希望本文可以对你起到帮助。
