class ListNode():
def __init__(self, x):
self.val = x
self.next = None
class Solution():
def partition(self, head, x):
h1 = t1 = ListNode(-1)
h2 = t2 = ListNode(-1)
cur = head
while cur:
if cur.val < x:
t1.next = cur
t1 = t1.next
else:
t2.next = cur
t2 = t2.next
cur = cur.next
t1.next, t2.next = h2.next, None
return h1.next
if __name__ == "__main__":
head, head.next, head.next.next, head.next.next.next, head.next.next.next.next, head.next.next.next.next.next \
= ListNode(1), ListNode(4), ListNode(3), ListNode(2), ListNode(5), ListNode(2)
print(Solution().partition(head, 3))