原题
给定一个单链表和数值x，划分链表使得所有小于x的节点排在大于等于x的节点之前。
你应该保留两部分内链表节点原有的相对顺序。
样例
给定链表 1->4->3->2->5->2->null，并且 x=3
返回** 1->2->2->4->3->5->null
**
解题思路
- 链表问题 - 建立两个Dummy Node
- 顺序遍历整条链表，小于的和大于等于的分别连上不同的dummy node，最后把两串连一起
完整代码
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def partition(self, head, x):
"""
:type head: ListNode
:type x: int
:rtype: ListNode
"""
leftDummy = ListNode(0)
rightDummy = ListNode(0)
left, right = leftDummy, rightDummy
while head != None:
if head.val < x:
left.next = head
left = left.next
else:
right.next = ListNode(head.val)
right = right.next
head = head.next
left.next = rightDummy.next
return leftDummy.next
