• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

leetcode刷题_PYTHON(8):链表(8)分隔链表

开发技术 开发技术 4小时前 2次浏览

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

你应当 保留 两个分区中每个节点的初始相对位置。

leetcode刷题_PYTHON(8):链表(8)分隔链表

 

这道题最简单的解题方式,就是我们创建两个小链表和大链表。
然后循环head,当head.val小于x时,追加到小链表,否则添加到大链表
最终将小链表与大链表合并。然后将大链表的链尾置为None。

当然,为了熟悉链表操作,写了一种寻找第一个大链表头的解法。
创建一个空链表,然后循环判断head,当head.val小于x,则直接拼接ret.next = head
当找到第一个大于等于x的val时,设置为刚才我们创建的大链表头,之后进行对比插入。
这个解法是为了进一步熟悉链表操作,自娱自乐…

class Solution:
    def partition(self, head, x):
        if not head:
            return head
        small = ListNode()
        sm = small
        large = ListNode()
        lg = large
        while head:
            if head.val < x:
                sm.next = head
                sm = sm.next
            else:
                lg.next = head
                lg = lg.next
            head = head.next
        lg.next = None
        sm.next = large.next
        return small.next

作者:qingfengpython
链接:https://leetcode-cn.com/problems/partition-list/solution/86fen-ge-lian-biao-chuang-jian-da-xiao-l-gy5y/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

 


程序员灯塔
转载请注明原文链接:leetcode刷题_PYTHON(8):链表(8)分隔链表
喜欢 (0)