leetcode_86. 分隔链表

举报
悲恋花丶无心之人 发表于 2021/02/03 01:09:32 2021/02/03
【摘要】 目录 一、题目内容 二、解题思路 三、代码 一、题目内容 给你一个链表和一个特定值 x ,请你对链表进行分隔,使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入:head = 1->4->3->2->5->2, x = 3 输出:1-&gt...

目录

一、题目内容

二、解题思路

三、代码


一、题目内容

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

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

示例:

输入:head = 1->4->3->2->5->2, x = 3
输出:1->2->2->4->3->5

二、解题思路

创建两个链表,一个存放小于x的一个存放大于x的,顺序不动,最后将两个链表进行拼接即可。

三、代码


  
  1. # Definition for singly-linked list.
  2. class ListNode:
  3. def __init__(self, x):
  4. self.val = x
  5. self.next = None
  6. def __repr__(self):
  7. return str(self.val)
  8. class Solution:
  9. def partition(self, head: ListNode, x: int) -> ListNode:
  10. if not head:
  11. return head
  12. head1 = ListNode(0)
  13. head2 = ListNode(0)
  14. cur1 = head1
  15. cur2 = head2
  16. while head:
  17. if head.val < x:
  18. cur1.next = head
  19. head = head.next
  20. cur1 = cur1.next
  21. cur1.next = None
  22. else:
  23. cur2.next = head
  24. head = head.next
  25. cur2 = cur2.next
  26. cur2.next = None
  27. cur1.next = head2.next
  28. return head1.next
  29. if __name__ == '__main__':
  30. s = Solution()
  31. head_list = [1, 4, 3, 2, 5, 2]
  32. head = ListNode(head_list[0])
  33. cur = head
  34. for i in range(1, len(head_list)):
  35. cur.next = ListNode(head_list[i])
  36. cur = cur.next
  37. x = 3
  38. ans = s.partition(head, x)
  39. print(ans)

文章来源: nickhuang1996.blog.csdn.net,作者:悲恋花丶无心之人,版权归原作者所有,如需转载,请联系作者。

原文链接:nickhuang1996.blog.csdn.net/article/details/112171792

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。