QuickSort with LinkedList

Problem Description:

Sort the given doubly linked list using quicksort. Just complete the partition function using quicksort techniquetry to solve it in O(1) space .

Input:

In this problem, method takes two argument: the node1 and node2. The function should not read any input from stdin/console.
The struct Node has a data part which stores the data and a next pointer which points to the next element of the linked list.
There are multiple test cases. For each test case, this method will be called individually.

/* a node of the doubly linked list */
/*struct node
{
    int data;
    struct node *next;
    struct node *prev;
};
   struct node *lastNode(node *root)
{
    while (root && root->next)
        root = root->next;
    return root;
}

void _quickSort(struct node* l, struct node *h)
{
    if (h != NULL && l != h && l != h->next)
    {
        struct node *p = partition(l, h);
        _quickSort(l, p->prev);
        _quickSort(p->next, h);
    }
}

void quickSort(struct node *head)
{
    // Find last node
    struct node *h = lastNode(head);

    // Call the recursive QuickSort
    _quickSort(head, h);
}*/
node* partition(node *l, node *h){
    //Your code goes here
    node *pvt=h;
    node *lft=l,*rit=h->prev;
    int tmp;
    int lVal=lft->data;
    int rVal=rit->data;
    int pVal=pvt->data;
    bool f=0;
    while(1)
    {
        while(lft!=h)
        {
            if(lft->data>pVal)
            break;
            lft=lft->next;
        }
        if(lft==h)
        break;
        while(lft!=rit)
        {
            if(rit->data<=pVal)
            break;
            rit=rit->prev;
        }
        if(lft==rit)
        break;
        tmp=rit->data;
        rit->data=lft->data;
        lft->data=tmp;
    }
    tmp=pvt->data;
    pvt->data=lft->data;
    lft->data=tmp;
    return lft;

}