LeetCode Problem : Sort List

Problem

Sort a linked list in O(n log n) time using constant space complexity.

Code

ListNode *partition(ListNode *p,ListNode *q,ListNode *prev,
ListNode **head,ListNode **left,ListNode **right){
    ListNode *i = p,*j = p,*r = p;
    int x = i->val;
    while(j && j->next && j->next != q){
        if(j->next->val < x){
            swap(i->next->val,j->next->val);
            i = i->next;
            j = j->next;
        }
        else if(j->next->val == x){
            if(r == j){
                r = r->next;
                i = r;
                j = j->next;
            }
            else{
                ListNode *tmp = j->next;
                j->next = tmp->next;
                tmp->next = r->next;
                r->next = tmp;
                if(i == r)
                    i = r->next;
                r = r->next;
            }
        }
        else
            j = j->next;
    }
    if(r != i){
        ListNode *first = r->next;
        r->next = i->next;
        i->next = p;
        if(p == *head)
            *head = first;
        else
            prev->next = first;
        *left = first;
        *right = r;
    }
    else{
        *left = p;
        *right = r;
    }
    return i;
}
void qsList(ListNode *p,ListNode *q,ListNode *prev,ListNode **head){
    if(p == q)
        return;
    ListNode *left,*right;
    ListNode *i = partition(p,q,prev,head,&left,&right);
    qsList(left,p,prev,head);
    qsList(right->next,q,right,head);
}
ListNode *sortList(ListNode *head) {
    // IMPORTANT: Please reset any member data you declared, as
    // the same Solution instance will be reused for each test case.
    if(!head)
        return 0;
    qsList(head,0,0,&head);    
    return head;
}