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 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { 7 * val = x; 8 * next = null; 9 * } 10 * } 11 */ 12 public class Solution { 13 public ListNode partition(ListNode head, int x) { 14 if (head==null) return head; 15 ListNode less,greater,l,g; 16 ListNode curr=head; 17 less=new ListNode(-1); 18 greater=new ListNode(1); 19 l=less; 20 g=greater; 21 while (curr!=null){ 22 if (curr.val<x){ 23 less.next=curr; 24 less=less.next; 25 }else { 26 greater.next = curr; 27 greater=greater.next; 28 } 29 curr=curr.next; 30 } 31 less.next=g.next; 32 greater.next=null; 33 return l.next; 34 35 } 36 }
原文：http://www.cnblogs.com/birdhack/p/4078425.html