#include <iostream>

struct ListNode 
{
    int val;
    ListNode *next;
  
    ListNode(int x = 0) : val(x), next(NULL) {}
};


ListNode * PartitionList(ListNode *head, int x)
{
    ListNode* less = NULL;
    ListNode* notLess = NULL;
    ListNode** lp = &less;
    ListNode** lnp = &notLess;

    while(head)
    {
        if (head->val < x)
        {
            *lp = head;
            lp = &(head->next);
        }
        else
        {
            *lnp = head;
            lnp = &(head->next);
        }

        head = head->next;
    }

    *lp = notLess;
    *lnp = NULL;

    return less;
}


using namespace std;

void PrintList(ListNode* h)
{
    while(h)
    {
        cout << h->val << ',';
        h = h->next;
    }

    cout << endl;
}

int main(int argc, char** argv)
{
    int A[] = {1,4,3,2,5,2};
    int n =sizeof(A)/sizeof(int);
    ListNode L[n];

    for (int i = 0; i < n-1; ++i)
    {
        L[i].val = A[i];
        L[i].next = L+(i+1);
    }
    L[n-1].val = A[n-1];
    
    PrintList(L);
    PrintList(PartitionList(L, 3));
    return 0;
}