LeetCode 86. Partition List 20170612

快来打我* 2021-12-23 11:49 148阅读 0赞

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.

For example,  
Given `1->4->3->2->5->2` and *x* = 3,  
return `1->2->2->4->3->5`.

题目大意：给定一个list和1个值值，把list分为两部分，小于x的放在前，大于等于x的放在后，两部分各自保持原有顺序

解题思路：用头结点的方法能够较好的解决这道题。创建两个头结点head1和head2，head1是小于x值的节点的链表，head2大于等于x值的节点的链表。遍历整个链表，把小于x的节点加到head1链表，把大于等于x的节点加到head2链表。

![1038316-20170612154914946-1120122997.png][]

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

转载于:https://www.cnblogs.com/fangdai/p/6993371.html

[1038316-20170612154914946-1120122997.png]: /images/20211223/4ae78bed337b4510ab9b882be2deec4b.png

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关 LeetCode86——Partition List

LeetCode86——Partition List 将链表按某个值划分，小的节点在前，大的节点在后，整体仍然保持原来的大小顺序。 ------------------

左手的ㄟ右手/ 2022年08月20日 04:11/ 0 赞/ 116 阅读

相关【leetcode每日一题】NO86.Partition List

题目：Given a linked list and a value x, partition it such that all nodes less than x come

拼搏现实的明天。/ 2022年08月04日 04:05/ 0 赞/ 131 阅读

相关 leetcode 86. Partition List

Given a linked list and a value x, partition it such that all nodes less than x come bef

阳光穿透心脏的1/2处/ 2022年06月08日 02:27/ 0 赞/ 135 阅读

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

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

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

相关 86. Partition List

/ Definition for singly-linked list. struct ListNode { int val

╰半夏微凉°/ 2022年04月03日 13:28/ 0 赞/ 123 阅读

相关【Leetcode】86. Partition List

Given a linked list and a value x, partition it such that all nodes less than xcome befo

Love The Way You Lie/ 2022年02月23日 12:18/ 0 赞/ 132 阅读

相关 LeetCode 86. Partition List 20170612

Given a linked list and a value x, partition it such that all nodes less than x come bef

快来打我*/ 2021年12月23日 11:49/ 0 赞/ 149 阅读

相关 [LeetCode] 86. Partition List_Medium tag: Linked List

Given a linked list and a value x, partition it such that all nodes less than x come bef

悠悠/ 2021年12月11日 22:57/ 0 赞/ 157 阅读

相关 leetcode--Partition List

Given a linked list and a value x, partition it such that all nodes less than x come bef

╰+哭是因爲堅強的太久メ/ 2021年10月25日 12:40/ 0 赞/ 178 阅读