进阶 - 5(分割链表)"/>
Python算法进阶 - 5(分割链表)
给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
来源:力扣(LeetCode)
链接:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution(object):def partition(self, head, x):before = before_head = ListNode(0)after = after_head = ListNode(0)while head:if head.val < x:before.next = headbefore = before.nextelse:after.next = headafter = after.nexthead = head.nextafter.next = Nonebefore.next = after_head.nextreturn before_head.next
这道题,自己虽然想到了大概,但是方法太low超时了,看下官方大神写的,借鉴思路,首先是创建一个哑节点(也及时L.nil)。
灵活运用,以前只局限于双链表才会有哑节点。
好处在于:为了算法实现更容易,我们使用了哑节点初始化。不能让哑节点成为返回链表中的一部分,因此在组合两个链表时需要向前移动一个节点。
思路:
用两个指针创建两个链表,小于x占一个链表,其他的是另一个链表。当第二个链表没有节点的时候,就可以将原来的两个链表进行连接起来就可以了。
see you 细品!!!
更多推荐
Python算法进阶 - 5(分割链表)
发布评论