LeetCode 分隔链表

超、凢脫俗 2023-06-04 13:59 7阅读 0赞

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

### 题目大意 ###

略。

### 分析 ###

空间复杂度 O(1) 的做法蛮有意思的，另外加头结点可以少写很多代码。

### 代码如下 ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /**
     2  * Definition for singly-linked list.
     3  * struct ListNode {
     4  *     int val;
     5  *     ListNode *next;
     6  *     ListNode(int x) : val(x), next(NULL) {}
     7  * };
     8  */
     9 class Solution {
    10 public:
    11     ListNode* partition(ListNode* head, int x) {
    12         ListNode *leftH, *leftT, *rightH, *rightT, *p = head;
    13         leftH = leftT = new ListNode(0);
    14         rightH = rightT = new ListNode(0);
    15         
    16         while(p != NULL) {
    17             if(p->val < x) {
    18                 leftT->next = p;
    19                 leftT =leftT->next;
    20                 
    21             }
    22             else if(p->val >= x) {
    23                 rightT->next = p;
    24                 rightT = rightT->next;
    25             }
    26             p = p->next;
    27         }
    28         
    29         leftT->next = rightH->next;
    30         rightT->next = NULL;
    31         
    32         return leftH->next;
    33     }
    34 };

转载于:https://www.cnblogs.com/zaq19970105/p/11349019.html

[https_leetcode-cn.com_problems_partition-list]: https://leetcode-cn.com/problems/partition-list/
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/3fbbc2799edd4bb8895b79b28373fc6c.png

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode 86. 分隔链表

题目题目链接思路拿两个链表，一个记录小于目标值，一个记录大于等于目标值，最后合并两个链表即可；代码class Solution {public: ListNode*...

- 日理万妓/ 2024年05月08日 06:07/ 0 赞/ 36 阅读

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

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

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

相关 (链表专题) 725. 分隔链表 ——【Leetcode每日一题】

725. 分隔链表给你一个头结点为 `head` 的单链表和一个整数 `k` ，请你设计一个算法将链表分隔为 `k` 个连续的部分。每部分的长度应该尽可能的相等：任

我不是女神ヾ/ 2024年03月24日 17:44/ 0 赞/ 12 阅读

相关 LeetCode 分隔链表

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

超、凢脫俗/ 2023年06月04日 13:59/ 0 赞/ 8 阅读

相关 LeetCode 725. 分隔链表

给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为

小灰灰/ 2023年01月12日 10:24/ 0 赞/ 109 阅读

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

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

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

相关 Leetcode 86. 分隔链表

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

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

相关 [Leetcode][python]Partition List/分隔链表

题目大意给定一个链表以及一个目标值，把小于该目标值的所有节点都移至链表的前端，大于或等于目标值的节点移至链表的尾端，同时要保持这两部分在原先链表中的相对位置。解题

Love The Way You Lie/ 2022年06月06日 02:00/ 0 赞/ 145 阅读

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

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

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

相关 LeetCode86. 分隔链表

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

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