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.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
解题思路：
只需记录小于3的最后一个指针和大于3的第一个指针即可，另外，如有创建一个ListNode result指向head可以减少代码长度，这个给出最简单的JAVA实现：
public ListNode partition(ListNode head, int x) {
if (head == null || head.next == null)
return head;
ListNode temp = head, firstMin = head;
if (head.val >= x) {
while (firstMin.next != null) {
if (firstMin.next.val < x) {
head = firstMin.next;
firstMin.next = firstMin.next.next;
head.next = temp;
break;
}
firstMin = firstMin.next;
}
}
if (head.val >= x)
return head;
firstMin = head;
temp=head.next;
while (temp != null && temp.val < x) {
firstMin = firstMin.next;
temp = temp.next;
}
if(temp==null)
return head;
ListNode firstMax=temp,lastMax=temp;
temp=temp.next;
while(temp!=null){
if(temp.val<x){
firstMin.next=temp;
firstMin=firstMin.next;
}else{
lastMax.next=temp;
lastMax=lastMax.next;
}
temp=temp.next;
}
firstMin.next=firstMax;
lastMax.next=null;
return head;
}
原文：http://www.cnblogs.com/tonyluis/p/4515644.html