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.

Partition List.cpp

/**
 * 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
        ListNode preHead(-1);
        preHead.next = head;
        ListNode left(-1);
        ListNode right(-1);
        
        ListNode* pHead = &preHead;
        ListNode* pLeft = &left;
        ListNode* pRight = &right;
        while(pHead->next != NULL) {
            int v = pHead->next->val;
            if(v < x) {
                pLeft->next = pHead->next;
                pLeft = pLeft->next;
            } else {
                pRight->next = pHead->next;
                pRight = pRight->next;
            }
            
            pHead = pHead->next;

        }
        pRight->next = NULL;
        pLeft->next = right.next;
        return left.next;
    }
};