题目要求：
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.
Examples：
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
解题思路：
- 使用两个链表: < target ：插入到less_head链表里；> target ：插入到more_head链表里，最后将两个链表相连接。
- 示意图
代码：
class ListNode():
def __init__(self, x):
self.val = x
self.next = None
def __repr__(self):
if self:
return "{} -> {}".format(self.val, repr(self.next))
class Solution(object):
def partition(self, head, x):
"""
:type head: ListNode
:type x: int
:rtype: ListNode
"""
less_head = ListNode(0)
more_head = ListNode(0)
less_ptr = less_head
more_ptr = more_head
while head:
if head.val < x:
less_ptr.next = head
less_ptr = head
head = head.next
less_ptr.next = None
else:
more_ptr.next = head
more_ptr = head
head = head.next
more_ptr.next = None
less_ptr.next = more_head.next
return less_head.next
if __name__ == "__main__":
head, head.next, head.next.next = ListNode(1), ListNode(5), ListNode(3)
head.next.next.next, head.next.next.next.next = ListNode(3), ListNode(4)
head.next.next.next.next.next, head.next.next.next.next.next.next = ListNode(4), ListNode(5)
print(Solution().partition(head, 4))
