LeetCode 0086 - Partition List

/**
 * 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* low = new ListNode(0);
        ListNode* high = new ListNode(0);
        ListNode* base_low = low;
        ListNode* base_high = high;
        while(head){
            if(head->val < x)
                low->next = head, low = low->next;
            else
                high->next = head, high = high->next;
            head = head->next; 
        }
        high->next = NULL;
        low->next = base_high->next;
        return base_low->next;
    }
};