【LeetCode力扣】86. 分隔链表

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