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 class Solution { 2 public ListNode partition(ListNode head, int x) { 3 if(head==null||head.next==null) return head; 4 ListNode big = new ListNode(0); 5 ListNode small = new ListNode(0); 6 ListNode smallhead = small; 7 ListNode bighead = big; 8 while(head!=null){ 9 if(head.val<x){ 10 small.next = head; 11 small = head; 12 } 13 else{ 14 big.next = head; 15 big = head; 16 } 17 head = head.next; 18 } 19 big.next = null; 20 small.next = bighead.next; 21 return smallhead.next; 22 } 23 24 }
原文：http://www.cnblogs.com/zle1992/p/7727216.html