• LeetCode 86. 分隔链表


    86. 分隔链表

    题目:给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
    你应当 保留 两个分区中每个节点的初始相对位置。
    链接 https://leetcode.cn/problems/partition-list/

    个人思路

    1. 双指针:
      (1)使用left记录当前走过的最后一个小于 x 的节点,使用right记录遇到的即将走过的小于 x 的节点的前一个节点。如对于[ 0, 1, 7, 3, 5, 2, 8, 9],当left在1的位置时,right走到7的位置,接下来使用temp记录值为3的节点,当right.next.val < x开始交换:
    temp = right.next
    # 将right.next接到right.next的下一个节点
    right.next = right.next.next
    # temp的下一个节点指向left的下一个节点
    # print(right.val,left.val)
    temp.next = left.next
    left.next = temp
    left = left.next 
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    交换结束后即为[ 0, 1, 3, 7, 5, 2, 8, 9],此时left为3,left.next还是7,right还是7。
    (2)当right.val >= x时,移动right即可right = right.next
    (3)但上面那个双指针当开始时会出现left和right在同一个位置的情况,这时候当right.next.val < x进行交换时会出现问题,
    我们来具体分析一下每一步得到的结果:首先设置一个dummy(-1,head)虚拟结点指向head,方便后面返回头结点。这时候,left和right都在dummy(因为我们需要上一个结点才能进行指向,即如果right=dummy.next=head时,如果right.val < x时,由于我们不知道上一个节点,我们根本无法进行有效的移动),但为了有效区分left和right,不让二者指向一个dummy,否则会该链会因为right.next = right.next.next和left = left.next 一次跳两步的原因越来越短

    dummy = ListNode(-1,head)
    left = dummy
    right = ListNode(-1,head)
    
    • 1
    • 2
    • 3
    temp = right.next  # 得到temp = 0
    # 将right.next接到right.next的下一个节点
    right.next = right.next.next   # 得到[-1,1, 7, 3, 5, 2, 8, 9]
    # temp的下一个节点指向left的下一个节点
    temp.next = left.next  # 此时left为dummy,因为left和right不是同一个,所以left.next.val=0,对temp及其后面得到[0, 0, 1, 7, 3, 5, 2, 8, 9]
    left.next = temp # 此时left和right均为dummy,left.next.val=0,对head及其后面得到[0, 0, 1, 7, 3, 5, 2, 8, 9]
    left = left.next 
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    1. 好吧,上面解释的不是很清楚,但解决上面的问题只需加一个判断left == right即可,如果二者一样,则二者一起向右移动即可。
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
            if not head or not head.next:
                return head
    # 想过双虚拟结点来解决问题
    #         dummy2 = ListNode(0,head)
    #         dummy1 = ListNode(0,dummy2)
    #         left = dummy1
    #         right = dummy2
            dummy = ListNode(-1,head)
            left = dummy
            right = dummy
            while right.next:
                if right.next.val < x:
                    if left == right:
                        left = left.next
                        right = right.next
                    else:
                        # temp为小于 x 的节点
                        temp = right.next.val
                        temp2 = ListNode(temp)
                        # 将right.next接到right.next的下一个节点
                        right.next = right.next.next
                        # temp的下一个节点指向left的下一个节点
                        # print(right.val,left.val)
                        temp2.next = left.next
                        left.next = temp2
                        left = left.next   
                else:         
                    right = right.next
                # 测试每一步是否移动正确
                #   print(right.val,left.val)
                # la = dummy.next
                # ans = []
                # while la:
                #     ans.append(la.val)
                #     la = la.next
                # print(ans)
                    
            return dummy.next
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    1. 简化后如下:
    class Solution:
        def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
            if not head or not head.next:
                return head
            dummy = ListNode(-1,head)
            left = dummy
            right = dummy
            while right.next:
                if right.next.val < x:
                    if left == right:
                        left = left.next
                        right = right.next
                    else:
                        # temp为小于 x 的节点
                        temp = right.next
                        # 将right.next接到right.next的下一个节点
                        right.next = right.next.next
                        # temp的下一个节点指向left的下一个节点
                        temp.next = left.next
                        left.next = temp
                        left = left.next   
                else:         
                    right = right.next
            return dummy.next
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    复杂度分析
    时间复杂度: O(n),其中 n 是原链表的长度。我们对该链表进行了一次遍历。
    空间复杂度: O(1)

    官方思路

    我擦,我好蠢,原来可以将小的放一个链表,大的放另一个链表,然后合起来就行。

    1. 模拟
      (1)直观来说我们只需维护两个链表small 和 large 即可,small 链表按顺序存储所有小于 x 的节点,large 链表按顺序存储所有大于等于 x 的节点。遍历完原链表后,我们只要将 small 链表尾节点指向large 链表的头节点即能完成对链表的分隔。
      (2)为了实现上述思路,我们设 smallHead 和 largeHead 分别为两个链表的哑节点,即它们的 next 指针指向链表的头节点,这样做的目的是为了更方便地处理头节点为空的边界条件。同时设 small 和 large 节点指向当前链表的末尾节点。开始时 smallHead=small,largeHead=large。随后,从前往后遍历链表,判断当前链表的节点值是否小于 x,如果小于就将 small 的 next 指针指向该节点,否则将 large 的 next 指针指向该节点。
      (3)遍历结束后,我们将 large 的 next 指针置空,这是因为当前节点复用的是原链表的节点,而其 next 指针可能指向一个小于 x 的节点,我们需要切断这个引用。同时将 small 的 next 指针指向 largeHead 的 next 指针指向的节点,即真正意义上的 large 链表的头节点。最后返回 smallHead 的 next 指针即为我们要求的答案。
    class Solution:
        def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
            if not head or not head.next:
                return head
            small = ListNode(-1,head)
            smallhead = small
            large = ListNode(-1,head)
            largehead = large
            while head:
                if head.val < x:
                    small.next = head
                    small = small.next
                else:         
                    large.next = head
                    large = large.next
                head = head.next
            large.next = None
            small.next = largehead.next
            return smallhead.next
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    参考:
    作者:LeetCode-Solution
    链接:https://leetcode.cn/problems/partition-list/solution/fen-ge-lian-biao-by-leetcode-solution-7ade/

  • 相关阅读:
    快速修复“找不到xinput1_3.dll无法继续执行此代码的”问题的5个方法
    C专家编程 第6章 运行的诗章:运行时数据结构 6.11 有用的C语言工具
    用正则表达式处理文本--1
    【组成原理-存储】关于交叉存储器检测访问冲突的一种算法
    京东资深架构师推荐学习6本实战文档:Redis+Nginx+MySQL+JVM....
    没有不写注释的程序员,如果有,一定没看过别人的代码?
    从WEB到PWA 开发-发布-安装
    完美解决Django项目生成的requirements.txt文件不能使用的问题
    中级深入--day16
    Flink系列之Flink之Time和WaterMark深入剖析
  • 原文地址:https://blog.csdn.net/weixin_48127034/article/details/126481316