Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
Example:
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def partition(self, head, x):
"""
:type head: ListNode
:type x: int
:rtype: ListNode
"""
if head==None or head.next==None:
return head
head1=head
count1=0
head2=head
count2=0
start1_head=None
start2_head=None
while head!=None:
if head.val<x:
tmp_node=ListNode(head.val)
if count1==0:
head1=tmp_node
start1_head=head1
else:
head1.next=tmp_node
head1=tmp_node
count1+=1
else:
tmp_node=ListNode(head.val)
if count2==0:
head2=tmp_node
start2_head=head2
else:
head2.next=tmp_node
head2=tmp_node
count2+=1
head=head.next
if start1_head==None:
return start2_head
else:
head1.next=start2_head
return start1_head