[LeetCode] 86. Partition List_Medium tag: Linked List

悠悠 2021-12-11 22:57 157阅读 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.

Example:

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

这个题目就是利用两个dummy node，leftDummy 代表小于x的那些node，rightDummy 代表大于等于x的那些node，最后将两者加起来即可。

Code

class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None
    
    class Solution:
        def partitionList(self, head, x):
            leftDummy, rightDummy = ListNode(0), listNode(0)
            left, right = leftDummy, rightDummy
            while head:
                if head.val < x:
                    left.next = head
                    left = left.next
                else:
                    right.next = head
                    right = right.next
                head = head.next
            left.next = rightDummy.next
            right.next = None
            return leftDummy.next

转载于:https://www.cnblogs.com/Johnsonxiong/p/10801691.html

发表评论取消回复

表情：

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

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

相关阅读

相关 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 赞/ 124 阅读

相关【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 赞/ 158 阅读

相关 [LeetCode] 206. Reverse Linked List_Easy tag: Linked List

Reverse a singly linked list. Example: Input: 1->2->3->4->5->NULL Output: 5->4

今天药忘吃喽~/ 2021年12月11日 22:55/ 0 赞/ 193 阅读

相关 [LeetCode] 234. Palindrome Linked List_Easy tag: Linked List

Given a singly linked list, determine if it is a palindrome. Example 1: Input: 1->

小咪咪/ 2021年11月16日 07:20/ 0 赞/ 230 阅读