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.
Analysis:
The first element that is not less than x is the point of partition. We record this node and its predecessor. Once we encount a node that is less than x later, we insert it between the point and its predecessor, then update the predecssor to this node.
Solution:
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 || head.next==null) return head; 15 ListNode preHead = new ListNode(-1); 16 preHead.next = head; 17 ListNode preStart = null,start=null; 18 ListNode cur = head; 19 ListNode pre = preHead; 20 21 while (cur.val<x && cur.next!=null){ 22 pre = cur; 23 cur = cur.next; 24 } 25 26 if (cur.next==null) return head; 27 28 start = cur; 29 preStart = pre; 30 pre = cur; 31 cur = cur.next; 32 while (cur!=null){ 33 if (cur.val<x){ 34 pre.next = cur.next; 35 preStart.next = cur; 36 cur.next = start; 37 preStart = cur; 38 cur = pre.next; 39 } else { 40 pre = cur; 41 cur = cur.next; 42 } 43 } 44 45 return preHead.next; 46 } 47 }
原文：http://www.cnblogs.com/lishiblog/p/4100959.html