链表21 -- 分割链表

心已赠人 2022-05-25 08:48 203阅读 0赞

1、题目:

Given a linked list and a value *x*, partition it such that all nodes less than *x* come before nodes greater than or equal to *x*.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

Input: head = 1->4->3->2->5->2, x = 3
    Output: 1->2->2->4->3->5

2、解答：思想就是，用一个指针指向比x小的值，另外一个值指向比它大的值。然后合并两个链表

3、C++代码：

class Solution {
    public:
        ListNode* partition(ListNode* head, int x) {
            if(!head)
                return head;
            ListNode *curr = head;
            ListNode *dummy = new ListNode(0);
            ListNode *dummy1 = new ListNode(0);
            ListNode *p = dummy;
            ListNode *q = dummy1;
            while(curr){
                if(curr->val < x){
                    p->next = curr;
                    p = p->next;
                }else{
                    q->next = curr;
                    q = q->next;
                }
                curr = curr->next;
            }
            q->next = NULL;
            p->next = dummy1->next;
            return dummy->next;
        }
    };

python代码：

class Solution:
        def partition(self, head, x):
            """
            :type head: ListNode
            :type x: int
            :rtype: ListNode
            """
            head1 = l1 = ListNode(0)
            head2 = l2 = ListNode(0)
            
            while head:
                if head.val < x:
                    l1.next = head
                    l1 = l1.next
                else:
                    l2.next = head
                    l2 = l2.next
                head = head.next
                
            l2.next = None
            l1.next = head2.next
            return head1.next

发表评论取消回复

表情：

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

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

相关阅读

相关【Java版oj】链表分割

目录一、原题再现二、问题分析三、完整代码 -------------------- > 一、原题再现 > > [链表分割\_牛客题霸\_牛客网][Link

我不是女神ヾ/ 2024年04月01日 09:03/ 0 赞/ 91 阅读

相关【链表OJ题 5】牛客 CM11 链表分割

目录题目来源：代码实现： 1.带哨兵位的头结点 2.不带哨兵位的头结点思路分析： 1.带哨兵位的头结点实现过程：易错点： 2.不带哨兵位的头结点

落日映苍穹つ/ 2023年09月27日 19:30/ 0 赞/ 26 阅读

相关链表分割（数据结构基础回顾）（链表）

编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前给定一个链表的头指针 ListNode\ pHead，请返回重新排列后的链表的头指针

╰半橙微兮°/ 2023年02月20日 14:00/ 0 赞/ 18 阅读

相关【链表】 LeetCode21. 合并两个有序链表

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

一时失言乱红尘/ 2022年12月02日 13:38/ 0 赞/ 188 阅读

相关 LeetCode 21. 合并两个有序链表（链表）

上一篇博客：[LeetCode 20. 有效的括号（栈、字符串）][LeetCode 20.] > 写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accept

左手的ㄟ右手/ 2022年11月28日 13:51/ 0 赞/ 263 阅读

相关链表----21. 合并两个有序链表

【题目】将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例 1： ![在这里插入图片描述][watermark_typ

「爱情、让人受尽委屈。」/ 2022年11月16日 01:54/ 0 赞/ 255 阅读

相关分割链表算法

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。需要保证分割链表的稳定性。

素颜马尾好姑娘i/ 2022年09月02日 07:50/ 0 赞/ 207 阅读

相关链表分割（解题报告）

题目描述编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前给定一个链表的头指针 ListNode\ pHead，请返回重新

刺骨的言语ヽ痛彻心扉/ 2022年06月15日 09:00/ 0 赞/ 176 阅读

相关链表21 -- 分割链表

1、题目: Given a linked list and a value x, partition it such that all nodes less than x c

心已赠人/ 2022年05月25日 08:48/ 0 赞/ 204 阅读

相关链表--单向链表

单向链表实现 class Node { constructor(element) { this.element = element;

刺骨的言语ヽ痛彻心扉/ 2021年12月03日 06:45/ 0 赞/ 476 阅读