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.

/**

 * 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) {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

         if(head == NULL) return head;

        ListNode *pre , *firstLarger, * preCur, * cur;

        pre = NULL; firstLarger = head;

        while(firstLarger  && firstLarger->val < x){

            pre = firstLarger;

            firstLarger = firstLarger ->next;

        }

        if(firstLarger == NULL) return head;

        preCur = firstLarger;

        cur = preCur->next;

        while(cur != NULL){

            if( cur->val >= x){

                preCur = cur;

                cur = cur->next;

                continue;

            }

            preCur->next = cur->next;

            cur->next = firstLarger;

            if(pre == NULL){

                pre = cur;

                head = cur;

            }else{

                pre->next = cur;

                pre = cur;

            }

            cur = preCur ->next;

        }

        return head;

    }

};