【LeetCode力扣】86. 分隔链表

心已赠人 2024-03-27 18:47 17阅读 0赞

![403da28d74c14e7abff23a14f4b4162b.png][]

**目录**

1、题目介绍

2、解题思路

2.1、双链表双指针

2.2、代码描述

![69f35379d10346e7bbf19d1d61fd3640.gif][]

## 1、题目介绍 ##

**原题链接：**[86. 分隔链表 - 力扣（LeetCode）][86. _ - _LeetCode]

![73b90090d50a450eb972cce81d06f15d.png][]

**示例 1：**

![865e0b69eda643f2ac32f624125c771d.png][]

> **输入：**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、解题思路 ##

> 根据题意，考虑通过「新建两个链表」实现原链表分割，算法流程为：
> 
> 1.  新建两个链表small 和BigEqu ，分别用于链接小于标志数x的结点和大于等于标志数 x 的结点。
> 2.  遍历链表head并依次比较各节点值 head->val 和 x 的大小，若head->val < x ,则将head指向的该结点添加到链表 small 最后面。若head->val >= x，则将head指向的该结点添加到链表BigEqu最后面。
> 3.  遍历完成后，拼接small 和BigEqu 链表。
> 4.  最终判断头结点并返回。

![23a8d0fb04854d17a2c6e0e5c3246f2c.png][]

### 2.1、双链表双指针 ###

> 首先比较head->val与x，发现此时head->val小于x，因此放入small链表中，此时small的链头smallH和链尾smallT都指向结点1。head指向下一个结点。

![5524c7a86f094f96a5d2805a934068f2.png][]

> 继续比较head->val与x，发现此时head->val大于x，因此放入BigEqu链表中，此时BigEqu的链头BigEquH和链尾BigEquT都指向结点4。head指向下一个结点。

![5b2b8d63612b4bad898d856f77d071f5.png][]

> 继续比较head->val与x，发现此时head->val等于x，因此放入BigEqu链表中，此时BigEqu的链尾BigEquT指向结点3。head指向下一个结点。

![e2d863e3176f44628e28d604f3c3f5d2.png][]

> 继续比较head->val与x，发现此时head->va小于x，因此放入small链表中，此时small的链尾smallT指向结点2。head指向下一个结点。

![cdd947cc42734c4f8798b9847d5cceb8.png][]

> 继续比较head->val与x，发现此时head->va大于x，因此放入BigEqu链表中，此时BigEqu的链尾BigEquT指向结点5。head指向下一个结点。

![e701d4cdd1a74e17933321ccbe09942c.png][]

> 继续比较head->val与x，发现此时head->va小于x，因此放入small链表中，此时small的链尾smallT指向结点2。head指向下一个结点，此时head为null，则停止循环。

![608c8beedbdb457ab72a2a65a4f2724d.png][]

> 此时以smallH为链头的链表就是**小于标志数 x 的结点集**，以BigEqu为链头的链表就是**大于等于标志数 x 的结点集**，只需要将small链表的链尾smallT的next指向BigEqu链表的链头，最后返回small的链头smallT 即可。

![cf6564e846e1441bbd241dcfda01f836.png][]

### 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
    }

![737a7a730750429baab31ebadb7b5528.png][]

更多【LeetCode刷题】 推荐：

[【LeetCode力扣】LCR170 使用归并排序的思想解决逆序对问题（详细图解）\_Hacynn的博客-CSDN博客![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://blog.csdn.net/zzzzzhxxx/article/details/133578735][LeetCode_LCR170 _Hacynn_-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133578735][【LeetCode力扣】75 快速排序的子过程partition（荷兰国旗问题）-CSDN博客![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://blog.csdn.net/zzzzzhxxx/article/details/133785886][LeetCode_75 _partition_-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133785886][【LeetCode力扣】297. 二叉树的序列化与反序列化-CSDN博客![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/f7995ccf3e52449dabad044167595f95.png][LeetCode_297. _-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133827375]

![bbe1754aa1b64f3dafbd5a9bd2b4cb2f.gif][]

**如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！**

**如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！**

**如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！**

[403da28d74c14e7abff23a14f4b4162b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/ac66bad31ef84dbfb9e22c092315a63a.png
[69f35379d10346e7bbf19d1d61fd3640.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/00cd63fbaec243b0a7062230be757041.png
[86. _ - _LeetCode]: https://leetcode.cn/problems/partition-list/description/?envType=list&envId=ixRuNo8f
[73b90090d50a450eb972cce81d06f15d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/523ce693c9de45ee80d7d8d56563eddc.png
[865e0b69eda643f2ac32f624125c771d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/782608b99785497c838f80963fef8967.png
[23a8d0fb04854d17a2c6e0e5c3246f2c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/d0aafc890d664fca85abd919cbbe3c31.png
[5524c7a86f094f96a5d2805a934068f2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/bbf8fd74e34a4f82b5b82b327c6dfbe1.png
[5b2b8d63612b4bad898d856f77d071f5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/c31f5b737f0d484f9df33cbfbc1d1ee8.png
[e2d863e3176f44628e28d604f3c3f5d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/052b7db2df7d40989d1ad5a0bd46d210.png
[cdd947cc42734c4f8798b9847d5cceb8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/deaa55316d264c618ba04541853d8d19.png
[e701d4cdd1a74e17933321ccbe09942c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/d5fa73800c4c4431b0d5e667a13889e9.png
[608c8beedbdb457ab72a2a65a4f2724d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/35d2807825db4410b2d98d57ad7101f1.png
[cf6564e846e1441bbd241dcfda01f836.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/35aa64a446a346728410842c88ed6506.png
[737a7a730750429baab31ebadb7b5528.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/28748b95e38f4924a6bb1de2870ba5b5.png
[icon-default.png_t_N7T8]: https://csdnimg.cn/release/blog_editor_html/release2.3.6/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N7T8
[LeetCode_LCR170 _Hacynn_-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133578735]: https://blog.csdn.net/zzzzzhxxx/article/details/133578735
[LeetCode_75 _partition_-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133785886]: https://blog.csdn.net/zzzzzhxxx/article/details/133785886
[LeetCode_297. _-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133827375]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/f7995ccf3e52449dabad044167595f95.png
[bbe1754aa1b64f3dafbd5a9bd2b4cb2f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/fb4462ed0bb2480bb6bd2a730dca0238.png

发表评论取消回复

表情：

评论列表（有 0 条评论，17人围观）

还没有评论，来说两句吧...

相关阅读

相关【LeetCode力扣】86. 分隔链表

![403da28d74c14e7abff23a14f4b4162b.png][] 目录 1、题目介绍 2、解题思路 2.1、双链表双指针 2.2、代码描述

心已赠人/ 2024年03月27日 18:47/ 0 赞/ 18 阅读

相关 LeetCode：86. Partition List分隔链表(C语言)

题目描述：给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。

淡淡的烟草味﹌/ 2023年01月01日 13:57/ 0 赞/ 64 阅读

相关【链表】 LeetCode86. 分隔链表

题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

绝地灬酷狼/ 2022年12月02日 13:38/ 0 赞/ 93 阅读

相关 86. 分隔链表

\\\ 解题思路新建两个链表头,按照归并排序的思想依次将小于x和大于x的节点插入表头后连接两个表 \\\ 代码 class Solution { p

比眉伴天荒/ 2022年10月28日 14:29/ 0 赞/ 112 阅读

相关力扣-86题（Java）-链表双指针

题目链接：[https://leetcode-cn.com/problems/partition-list/][https_leetcode-cn.com_problems_p

水深无声/ 2022年10月21日 11:59/ 0 赞/ 111 阅读

相关 86. 分隔链表

> 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。 > > 你应当保留两个分区中

左手的ㄟ右手/ 2022年10月07日 06:55/ 0 赞/ 116 阅读

相关 Leetcode 86. 分隔链表

题目重述给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。你应当保留两个分

朴灿烈づ我的快乐病毒、/ 2022年08月28日 05:00/ 0 赞/ 80 阅读

相关 LeetCode 86.Partition List (分隔链表)

题目描述：给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。示例:

àì夳堔傛蜴生んèń/ 2022年05月10日 10:14/ 0 赞/ 101 阅读

相关 LeetCode86. 分隔链表

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。示例: 输入

我会带着你远行/ 2022年05月10日 07:33/ 0 赞/ 125 阅读

相关 Leetcode算法Java全解答--86. 分隔链表

Leetcode算法Java全解答–86. 分隔链表文章目录 Leetcode算法Java全解答--86. 分隔链表题目想法

ゝ一纸荒年。/ 2022年04月03日 14:07/ 0 赞/ 111 阅读