qsort c++ 60ms


  • -1
    H

    '''
    /链表快速排序/

    class Solution {
    public:
    ListNode* list_qsort(ListNode begin, ListNode &tail) //tail用于获取排序后链表的尾节点
    {
    if(begin==NULL || begin->next==NULL)
    {
    tail = begin;
    return begin;
    }

        ListNode *head=NULL;
        ListNode *p = begin->next;
        begin->next = NULL;
        ListNode *np;
        
        bool tail_sorted = true;    //右边节点都等于分割节点,无需排序
        while(p!=NULL)
        {
            np = p->next;
            if(p->val<begin->val)
            {
                p->next = head;
                head = p;
            }
            else
            {
                if(p->val!=begin->val)
                {
                    tail_sorted = false;
                }
                p->next = begin->next;
                begin->next = p;
            }
            p = np;
        }
        
        ListNode* ntail;
        
        if(begin->next && begin->next->next)
        {
            if(tail_sorted)
            {
                ntail = begin;
                while(ntail->next)ntail=ntail->next;
            }
            else
            {
                begin->next = list_qsort(begin->next, tail);
                ntail = tail;
            }
        }
        else if(begin->next)
        {
            ntail = begin->next;
        }
        else
        {
            ntail = begin;
        }
        
        if(head && head->next)
        {
            head = list_qsort(head, tail);
            tail->next = begin;
        }
        else if(head)
        {
            head->next = begin;
        }
        else
        {
            head = begin;
        }
        
        tail = ntail;
        return head;
    }
    ListNode* sortList(ListNode* head) {
        ListNode *tail=NULL;
        return list_qsort(head, tail);
    }
    

    };
    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.