问题：

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.

解决：

① 将比给定的数x小的值放在左边，所有大于等于x值的节点放在右边，需要注意的是要求节点的原始相对位置不变！比如4->3->5都是大于等3的数，而且这保持了它们原来的相对位置 。

新建两个链表，分别用于存储小于x的值，大于等于x的值。然后将两个链表连到一起即可。

/**

 * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode(int x) { val = x; }  * }  */

class Solution {//1ms

    public ListNode partition(ListNode head, int x){         ListNode h1 = new ListNode(-1);//存放小于x的节点         ListNode h2 = new ListNode(-1);//存放大于x的节点         ListNode p1 = h1;         ListNode p2 = h2;         while(head != null){             if (head.val < x){                 p1.next = head;                 p1 = p1.next;             }else{                 p2.next = head;                 p2 = p2.next;             }             head = head.next;         }         p2.next = null;//p2指向最后的节点，若不加该句会出现内存越界         p1.next = h2.next;         return h1.next;     } }

② 首先找到第一个大于或等于给定值的节点，用题目中给的例子来说就是先找到4，然后再找小于3的值，每找到一个就将其取出置于4之前即可。

Original: 1 -> 4 -> 3 -> 2 -> 5 -> 2 

New:

Original: 4 -> 3 -> 2 -> 5 -> 2 

New:　  1

Original: 4 -> 3 -> 5 -> 2 

New:　  1 -> 2

Original: 4 -> 3 -> 5 

New:　  1 -> 2 -> 2

Original: 

New:　  1 -> 2 -> 2 -> 4 -> 3 -> 5 

/**

 * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode(int x) { val = x; }  * }  */ class Solution {//1ms     public ListNode partition(ListNode head, int x){         ListNode header = new ListNode(-1);         header.next = head;         ListNode pre = header;         while(pre.next != null && pre.next.val < x){             pre = pre.next;         }         if(pre.next == null) return header.next;//[],0的情况需要单独讨论         ListNode cur = pre.next;         while(cur.next != null){             if (cur.next.val < x){                 ListNode tmp = cur.next;                 cur.next = tmp.next;                 tmp.next = pre.next;                 pre.next = tmp;                 pre = tmp;             }else{                 cur = cur.next;             }         }         return header.next;     } }