- 描述
给定一个单链表和数值x,划分链表使得所有小于x的节点排在大于等于x的节点之前。
你应该保留两部分内链表节点原有的相对顺序。
- 样例
给定链表 1->4->3->2->5->2->null,并且 x=3
返回 1->2->2->4->3->5->null。
- Solution
利用二分思想,小于x的一个链表,大于x的一个链表,再整合两个链表。
"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param head: The first node of linked list
@param x: An integer
@return: A ListNode
"""
def partition(self, head, x):
# write your code here
headl, headr = ListNode(0), ListNode(0)
head2, head1 = headl, headr
if head is None:
return
while head is not None:
if x > head.val:
head1.next = head
head1 = head1.next
else:
head2.next = head
head2 = head2.next
head = head.next
head1.next = headl.next
head2.next = None
return headr.next
网友评论