Split

void split(node *head, int pivot, node** lt, node** gt)
{
    if (head == NULL)
        return;
 
    node *p1, *p2, *p3;
    p1 = head;
    *lt = (node*)malloc(sizeof(node));
    *gt = (node*)malloc(sizeof(node));
    p2 = lt;
    p3 = gt;
 
    while (p1 != NULL) {
        if (p1->value <= pivot) {
            p2->next = p1;
            p2 = p2->next;
        }
        else {
            p3->next = p1;
            p3 = p3->next;
        }
        p1 = p1->next;
    }
 
    p2->next = NULL;
    p3->next = NULL;
 
    p2 = *lt;
    p3 = *gt;
    *lt = *lt->next;
    *gt = *gt->next;
 
    free(p2);
    free(p3);
}