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,Given1->4->3->2->5->2
and x = 3,return1->2->2->4->3->5.

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if(head==NULL||head->next==NULL)
          return head;
        ListNode* small  = new ListNode(-1);
        ListNode* newSmall = small;
        ListNode* big = new ListNode(-1);
        ListNode* newBig = big;
        ListNode* p = head;
        
        while(p!=NULL)
        {
            if(p->val<x)
            {
                small->next = p;
                small = small->next;
            }
            else
            {
                big->next = p;
                big = big->next;
            }
            p = p->next;
        }
        big->next = NULL;
        small->next = newBig->next;
        
        return newSmall->next;
        
    }
};