目录
1、题目介绍
2、解题思路
2.1、双链表双指针
2.2、代码描述
1、题目介绍
原题链接：86. 分隔链表 - 力扣（LeetCode）
示例 1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2
输出：[1,2]
提示：
- 链表中节点的数目在范围 [0, 200] 内
- -100 <= Node.val <= 100
- -200 <= x <= 200
2、解题思路
根据题意，考虑通过「新建两个链表」实现原链表分割，算法流程为：
- 新建两个链表 small 和 BigEqu ，分别用于链接小于标志数 x 的结点和大于等于标志数 x 的结点。
- 遍历链表head并依次比较各节点值 head->val 和 x 的大小，若head->val < x ,则将head指向的该结点添加到链表 small 最后面。若head->val >= x，则将head指向的该结点添加到链表BigEqu最后面。
- 遍历完成后，拼接 small 和 BigEqu 链表。
- 最终判断头结点并返回。
2.1、双链表双指针
首先比较head->val与x，发现此时head->val小于x，因此放入small链表中，此时small的链头smallH和链尾smallT都指向结点1。head指向下一个结点。
继续比较head->val与x，发现此时head->val大于x，因此放入BigEqu链表中，此时BigEqu的链头BigEquH和链尾BigEquT都指向结点4。head指向下一个结点。
继续比较head->val与x，发现此时head->val等于x，因此放入BigEqu链表中，此时BigEqu的链尾BigEquT指向结点3。head指向下一个结点。
继续比较head->val与x，发现此时head->va小于x，因此放入small链表中，此时small的链尾smallT指向结点2。head指向下一个结点。
继续比较head->val与x，发现此时head->va大于x，因此放入BigEqu链表中，此时BigEqu的链尾BigEquT指向结点5。head指向下一个结点。
继续比较head->val与x，发现此时head->va小于x，因此放入small链表中，此时small的链尾smallT指向结点2。head指向下一个结点，此时head为null，则停止循环。
此时以smallH为链头的链表就是小于标志数 x 的结点集，以BigEqu为链头的链表就是大于等于标志数 x 的结点集，只需要将small链表的链尾smallT的next指向BigEqu链表的链头，最后返回small的 链头smallT 即可。
2.2、代码描述
循环的过程都比较好理解，就是最后合并链表时需要考虑特殊情况，如果没有小于标志数的结点时，此时返回的链头就不是smallH了，而是BigEqu的链头BigEquH。
struct ListNode* partition(struct ListNode* head, int x){
struct ListNode* smallH = NULL; //小于头
struct ListNode* smallT = NULL; //小于尾
struct ListNode* BigEquH = NULL; //大于等于头
struct ListNode* BigEquT = NULL; //大于等于尾
struct ListNode* next = NULL;
//小于连一起，大于等于连一起
while(head)
{
next = head->next; //用next保存head的next，然后将head->置为空
head->next = NULL; //确保此时的head的next置为空，不然可能会导致死循环报错
if(head->val < x) //小于标志数
{
if(smallH == NULL) //等于NULL表示第一次放入结点，
//此时链头链尾都指向同一个结点
{
smallH = smallT = head;
}
else //small的链尾的next指向head
{
smallT->next = head;
smallT = head;
}
}
else //大于等于标志数
{
if(BigEquH == NULL) //同理
{
BigEquH = BigEquT = head;
}
else
{
BigEquT->next = head;
BigEquT = head;
}
}
head = next; //head指向下一个结点
}
//判断是否可以尾接头
if(smallT != NULL) //当small链尾不为空，即small链表有结点时，
//才让small链尾连接BigEqu链头
{
smallT->next = BigEquH;
}
return smallH == NULL ? BigEquH : smallH; //当small链表没有结点时，返回链头BigEquH，
//否则返回链头smallH
}
更多【LeetCode刷题】 推荐：
【LeetCode力扣】LCR170 使用归并排序的思想解决逆序对问题（详细图解）_Hacynn的博客-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133578735【LeetCode力扣】75 快速排序的子过程partition（荷兰国旗问题）-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133785886【LeetCode力扣】297. 二叉树的序列化与反序列化-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133827375
如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！文章来源地址https://www.toymoban.com/news/detail-712830.html
如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！文章来源：https://www.toymoban.com/news/detail-712830.html
如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！
到了这里，关于【LeetCode力扣】86. 分隔链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
