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的节点，记为p，p前一个节点记为s，向后遍历链表，如果节点的值小于x,就把该节点插入到s后面，同时s后移一位。

为了方便，使用了哨兵节点。

java:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head==null||head.next==null)
            return head;
        ListNode  h =new ListNode(-1);
        h.next=head;
        ListNode p=head;
        ListNode s=h;
        while(p!=null){
            if(p.val>=x){
                break;
            }
            s=s.next;
            p=p.next;
        }
        ListNode q=p;
        while(p!=null){
            if(p.val<x){
                ListNode tmp=p.next;
                q.next=tmp;
                p.next=s.next;
                s.next=p;
                s=s.next;
            }
            q=p;
            p=p.next;
        }
        return h.next;
    }
}

c++：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        if(!head||!head->next)
            return head;
        ListNode * h =(ListNode *)malloc(sizeof(ListNode));
        h->next=head;
        ListNode *p=head;
        ListNode *s=h;
        while(p){
            if(p->val>=x){
                break;
            }
            s=s->next;
            p=p->next;
        }
        ListNode *q=p;
        while(p){
            if(p->val<x){
                ListNode *tmp=p->next;
                q->next=tmp;
                p->next=s->next;
                s->next=p;

                s=s->next;//后移一步
            }
            q=p;
            p=p->next;
        }
        return h->next;
    }
};

leetcode--Partition List