/**
 * 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 || head->next==NULL) return head;
        
        ListNode* pLarge;
        ListNode* pSmall;
        ListNode* pMid;
        
        if(head->val<x) pSmall=head;
        else
        {
            pLarge=head;
            pMid=head;
            while(pMid->next!=NULL && pMid->next->val>=x) pMid=pMid->next;
            if(pMid->next==NULL) return head;
            head=pMid->next;
            pMid->next=head->next;
            head->next=pLarge;
            pSmall=head;
        }
        
        while(true)
        {
            pMid=pSmall;
            
            while(pMid->next!=NULL && pMid->next->val>=x) pMid=pMid->next;
            if(pMid->next==NULL) break;
            
            pLarge=pMid->next;
            pMid->next=pLarge->next;
            pLarge->next=pSmall->next;
            pSmall->next=pLarge;
            
            while(pSmall->next!=NULL && pSmall->next->val<x) pSmall=pSmall->next;
            if(pSmall->next==NULL) break;
        }
        return head;
    }
};