- 描述
給定一個(gè)單鏈表和數(shù)值x职辅，劃分鏈表使得所有小于x的節(jié)點(diǎn)排在大于等于x的節(jié)點(diǎn)之前。
你應(yīng)該保留兩部分內(nèi)鏈表節(jié)點(diǎn)原有的相對(duì)順序戳葵。
- 樣例
給定鏈表 1->4->3->2->5->2->null筋量，并且 x=3
返回 1->2->2->4->3->5->null植袍。
- Solution
利用二分思想筋遭，小于x的一個(gè)鏈表打颤，大于x的一個(gè)鏈表，再整合兩個(gè)鏈表漓滔。
"""
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
