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

Love The Way You Lie 2022-06-06 02:00 166阅读 0赞

## 题目大意 ##

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

## 解题思路 ##

此题并不难，并且可以帮助理解链表。  
两个指针，一个负责收集比目标小的，一个收集大于等于目标的。

## 代码 ##

class Solution(object):
        def partition(self, head, x):
            """
            :type head: ListNode
            :type x: int
            :rtype: ListNode
            """
            dummy = ListNode(-1)
            dummy.next = head
            small_dummy = ListNode(-1)
            large_dummy = ListNode(-1)
    
            # small_prev和large_prev往后遍历增加，small_dummy和large_dummy则负责最后作为返回头结点
            small_prev = small_dummy
            large_prev = large_dummy
            while dummy.next:  # head第一个节点
                curr = dummy.next
                if curr.val < x:
                    small_prev.next = curr
                    small_prev = small_prev.next
                else:
                    large_prev.next = curr
                    large_prev = large_prev.next
                dummy = dummy.next
    
            large_prev.next = None  # 最后指针置为none
            small_prev.next = large_dummy.next  # large_dummy对应的是大链表的第一个数
            return small_dummy.next  # 返回的是small_dummy

## 总结 ##

发表评论取消回复

表情：

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

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

相关阅读

相关 86. 分隔链表

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

迷南。/ 2023年10月05日 21:24/ 0 赞/ 37 阅读

相关 LeetCode 分隔链表

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

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

相关 725. 分隔链表

题目来源 [725. 分隔链表][725.] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shado

ゝ一纸荒年。/ 2023年02月22日 10:42/ 0 赞/ 153 阅读

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

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

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

相关 725. 分隔链表

\\\ 解题思路 1.首先求出链表中一共有多少个元素n 2.然后通过n/k判断一共要分成几块 3.通过n%k判断多出来多少个节点,把他们分别分配到对应的块中去 \\\

ゝ一纸荒年。/ 2022年10月29日 06:26/ 0 赞/ 139 阅读

相关 86. 分隔链表

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

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

相关 86. 分隔链表

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

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

相关 725. 分隔链表

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

怼烎@/ 2022年09月12日 07:46/ 0 赞/ 172 阅读

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

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

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

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

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

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