LeetCode 分隔链表

超、凢脫俗 2023-06-04 13:59 122阅读 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 条评论，122人围观）

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

相关阅读

相关 LeetCode 86. 分隔链表

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

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

相关 leetcode86. 分隔链表

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

Dear 丶/ 2023年07月01日 15:55/ 0 赞/ 72 阅读

相关 leetcode 86 分隔链表

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

墨蓝/ 2023年06月21日 03:47/ 0 赞/ 48 阅读

相关 leetcode 86. 分隔链表

把小于（或者大于等于）的结点单独弄成一个链表，直接调整指针 class Solution { public: ListNode partit

短命女/ 2023年06月05日 08:27/ 0 赞/ 36 阅读

相关 LeetCode 分隔链表

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

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

相关 leetcode---86. 分隔链表

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

Bertha 。/ 2023年02月21日 11:54/ 0 赞/ 97 阅读

相关 LeetCode 725. 分隔链表

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

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

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

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

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

相关 Leetcode 86. 分隔链表

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

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

相关 LeetCode86. 分隔链表

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

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