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。创建DummyNode。2.记得将尾部节点的next置为null。
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; } 7 * } 8 */ 9 public class Solution { 10 public ListNode partition(ListNode head, int x) { 11 if (head == null || head.next == null) { 12 return head; 13 } 14 ListNode leftDummy = new ListNode(0); 15 ListNode rightDummy = new ListNode(0); 16 ListNode left = leftDummy; 17 ListNode right = rightDummy; 18 while (head != null) { 19 if (head.val < x) { 20 left.next = head; 21 left = left.next; 22 } else { 23 right.next = head; 24 right = right.next; 25 } 26 head = head.next; 27 } 28 left.next = rightDummy.next; 29 right.next = null; 30 return leftDummy.next; 31 } 32 }
原文：http://www.cnblogs.com/FLAGyuri/p/5314031.html