思路:
1. 空间复杂度为 o(n) 解法. 创建两个链表, 分别记录大于 x 和小于 x 的节点, 最后合并
2. o(1) 的空间复杂度解法. 四个指针, 分别指向小于 x 部分链表的头, 尾, 指向大于 x 部分链表的头, 尾
为了简单，我这里使用1的思路。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # @param {ListNode} head # @param {integer} x # @return {ListNode} def partition(self, head, x): head1=ListNode(0) head2=ListNode(0) h1flag=head1 h2flag=head2 while head!=None: if head.val<x: h1flag.next=head h1flag=h1flag.next head=head.next else: h2flag.next=head h2flag=h2flag.next head=head.next h2flag.next=None h1flag.next=head2.next return head1.next
原文：http://www.cnblogs.com/qiaozhoulin/p/4566632.html