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) {
        ListNode* sHead = nullptr, *sCurr = nullptr, *gHead = nullptr, *gCurr = nullptr;
        auto curr = head;
        while(curr)
        {
            if(curr->val < x)
            {
                if(!sHead)
                {
                    sHead = curr;
                    sCurr = curr;
                }
                else
                {
                    sCurr->next = curr;
                    sCurr = sCurr->next;
                }
            }
            else
            {
                if(!gHead)
                {
                    gHead = curr;
                    gCurr = curr;
                }
                else
                {
                    gCurr->next = curr;
                    gCurr = gCurr->next;
                }
            }
            curr = curr->next;
        }
        if(sCurr)sCurr->next = gHead;
        if(gCurr)gCurr->next = nullptr;
        return sHead? sHead : gHead;
    }
};