Partition LInked List such that all values less than x are on left and the rest on the right side.

PartitionLinkedList.cpp

Node* sendToOtherList(Node* otherSideList, Node* n)
{
    n->next = NULL;
    if (otherSideList)
    {
        otherSideList->next = n;
        otherSideList = otherSideList->next;
    }
    else
    {
        otherSideList = n;
    }
    return otherSideList;
}
Node* partitionList (Node* node, int middleValue)
{
    Node* current = node;
    Node* higher = NULL;
    Node* lower = NULL;
    Node* firstLow = NULL;
    while (current != NULL)
    {
        Node* tmp = current;
        current = current->next;
        tmp->next = NULL;
        if (tmp->data > middleValue)
        {
            higher = sendToOtherList(higher, tmp);
        }
        else
        {
            lower = sendToOtherList(lower, tmp);
            if (firstLow == NULL) firstLow = lower;
        }
    }
    lower->next = node;
    return firstLow;
}