leetcode_86. 分隔链表
【摘要】 目录
一、题目内容
二、解题思路
三、代码
一、题目内容
给你一个链表和一个特定值 x ,请你对链表进行分隔,使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入:head = 1->4->3->2->5->2, x = 3 输出:1->...
目录
一、题目内容
给你一个链表和一个特定值 x ,请你对链表进行分隔,使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入:head = 1->4->3->2->5->2, x = 3
输出:1->2->2->4->3->5
二、解题思路
创建两个链表,一个存放小于x的,一个存放大于x的,顺序不动,最后将两个链表进行拼接即可。
三、代码
-
# Definition for singly-linked list.
-
class ListNode:
-
def __init__(self, x):
-
self.val = x
-
self.next = None
-
-
def __repr__(self):
-
return str(self.val)
-
-
class Solution:
-
def partition(self, head: ListNode, x: int) -> ListNode:
-
if not head:
-
return head
-
head1 = ListNode(0)
-
head2 = ListNode(0)
-
cur1 = head1
-
cur2 = head2
-
while head:
-
if head.val < x:
-
cur1.next = head
-
head = head.next
-
cur1 = cur1.next
-
cur1.next = None
-
else:
-
cur2.next = head
-
head = head.next
-
cur2 = cur2.next
-
cur2.next = None
-
cur1.next = head2.next
-
return head1.next
-
-
-
if __name__ == '__main__':
-
s = Solution()
-
head_list = [1, 4, 3, 2, 5, 2]
-
head = ListNode(head_list[0])
-
cur = head
-
for i in range(1, len(head_list)):
-
cur.next = ListNode(head_list[i])
-
cur = cur.next
-
x = 3
-
ans = s.partition(head, x)
-
print(ans)
文章来源: nickhuang1996.blog.csdn.net,作者:悲恋花丶无心之人,版权归原作者所有,如需转载,请联系作者。
原文链接:nickhuang1996.blog.csdn.net/article/details/112171792
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)