/**

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

         ListNode *leftH, *leftT, *rightH, *rightT, *p = head;

         leftH = leftT = new ListNode();

         rightH = rightT = new ListNode();

         while(p != NULL) {

             if(p->val < x) {

                 leftT->next = p;

                 leftT =leftT->next;

             }

             else if(p->val >= x) {

                 rightT->next = p;

                 rightT = rightT->next;

             }

             p = p->next;

         }

         leftT->next = rightH->next;

         rightT->next = NULL;

         return leftH->next;

     }

 };