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.
1 public class Solution { 2 public ListNode partition(ListNode head, int x) { 3 ListNode safe = new ListNode(x-1); 4 ListNode pre = head; 5 ListNode cur = safe; 6 safe.next = head; 7 while(pre!=null && pre.val<x){ 8 cur = pre; 9 pre = pre.next; 10 } 11 if(pre==null){ 12 return head; 13 } 14 else{ 15 ListNode p = pre; 16 while(pre!=null){ 17 if(pre.val<x){ 18 ListNode temp = cur.next; 19 p.next =pre.next; 20 cur.next = pre; 21 pre.next = temp; 22 cur = pre; 23 pre =p.next; 24 } 25 else{ 26 p = pre; 27 pre = pre.next; 28 } 29 } 30 } 31 return safe.next; 32 } 33 }
原文：http://www.cnblogs.com/krunning/p/3542973.html
