141-解决链表partition

叁歲伎倆 2023-01-08 13:25 50阅读 0赞

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

输入: head = 1->4->3->2->5->2, x = 3  
输出: 1->2->2->4->3->5

**解题思路：**  
第一步：将链表拆分成两部分链表，一部分是小于X的节点，另外一部分是大于等于x的节点。  
第二步：拼装链表

ListNode *partition(ListNode *head, int x)
    {
        
        ListNode *head1 = new ListNode(0);//申请一个结点并初始化为0 
        ListNode *head2 = new ListNode(0);//申请一个结点并初始化为0 
        
        //将小于x的挂到head1上面 大于等于x的挂head2上面
        ListNode *p= head1, *q= head2; 
        
        while (head != NULL)
        {
        
            if (head->val < x)//val值小于x 
            {
        
                p->next = head;
                p = p->next;
            }
            else//val值大于等于x 
            {
        
                q->next = head;
                q= q->next;
            }
            head = head->next;//头结点向后移动 
        }
        
        p->next = head2->next;//两个子链进行拼接 
        q->next = NULL;//尾结点的next置为空 
        
        return head1->next;//返回合成后的新链的头结点 
        
    }

演示图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/30c265965f284b9e87235f9be46ba8b6.png

发表评论取消回复

表情：

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

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

相关阅读

相关 141.环形链表

打卡!!!每日一题今天给大家分享一道链表类型的题目，题目很简单，主要是处理的方法，本文主要有两道题，带着大家由第一道题过渡到第二道题目。题目1：141.环形链表

Bertha 。/ 2023年10月11日 17:56/ 0 赞/ 24 阅读

相关 141：环形链表

class Solution(object): def hasCycle(self, head): """

短命女/ 2023年10月09日 12:17/ 0 赞/ 23 阅读

相关 141. 环形链表

题目： [141. 环形链表][141.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_tex

﹏ヽ暗。殇╰゛Y/ 2023年02月12日 13:27/ 0 赞/ 24 阅读

相关 141. 环形链表

题目来源 [leetcode][] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_

╰+哭是因爲堅強的太久メ/ 2023年02月10日 05:20/ 0 赞/ 149 阅读

相关 141-解决链表partition

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

叁歲伎倆/ 2023年01月08日 13:25/ 0 赞/ 51 阅读

相关链表----141. 环形链表

【题目】给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来

朱雀/ 2022年11月16日 01:54/ 0 赞/ 182 阅读

相关 141. 环形链表

> 给定一个链表，判断链表中是否有环。 > > ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9

╰+哭是因爲堅強的太久メ/ 2022年10月07日 06:56/ 0 赞/ 182 阅读

相关 141. 环形链表（简单）

Leetcode链接：[141. 环形链表][141.] 题目描述 > 给定一个链表，判断链表中是否有环。 > > > 如果链表中有某个节点，可以通过连

小咪咪/ 2022年09月09日 02:09/ 0 赞/ 163 阅读

相关 141. 环形链表

[https://leetcode-cn.com/problems/linked-list-cycle/][https_leetcode-cn.com_problems_lin

系统管理员/ 2022年09月08日 00:21/ 0 赞/ 219 阅读

相关 LeetCode【141.环形链表】

题目描述 > 给定一个链表，判断链表中是否有环。思路 \ 1 还是使用快慢指针的思路进行遍历，如果有环的话，快慢指针总会相遇于一个结点；否则快指针也会走到`nul

小咪咪/ 2022年05月08日 12:24/ 0 赞/ 335 阅读