给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3

输出: 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) {

         if(head == NULL) return NULL;

         ListNode *left = head, *right, *pre;

         if(left->val >= x){

             pre = left;

             right = pre->next;

             while(right){

                 if(right->val < x){

                     pre->next = right->next;

                     right->next = left;

                     head = left = right;

                     right = pre->next;

                     break;

                 }

                 pre = right;

                 right = right->next;

             }

             if(right == NULL) return head;

         }

         else{

             while(left->next && left->next->val < x)

                 left = left->next;

             right = left->next;

             if(right == NULL) return head;

             pre = right;

         }

         while(right){

             if(right->val < x){

                 pre->next = right->next;

                 right->next = left->next;

                 left->next = right;

                 left = right;

                 right = pre->next;

                 continue;

             }

             pre = right;

             right = right->next;

         }

         return head;

     }

 };