30ms C++ solution for insertino Sort Lists


  • -1
    J

    /**

    • Definition for singly-linked list.
    • struct ListNode {
    • int val;
      
    • ListNode *next;
      
    • ListNode(int x) : val(x), next(NULL) {}
      
    • };
      */
      class Solution {
      public:

    the method complexity may be O(n), Is there any method to improve?

    ListNode *insertionSortList(ListNode *head) {
    if(head==NULL) return NULL;
    if(!head->next) return head;

        ListNode *pre,*p,*phead,*piter;
        ListNode *pivot=head;
        phead=head;
        pre=head;
        p=pre->next;
        
        int foundFlag;
        
        while(p){
            
            if(p->val<pivot->val && p->val<=phead->val){
                pre->next=p->next;
                p->next=phead;
                phead=p;
                
            }else if(p->val>=pivot->val && p->val>=pre->val){
                pre=pre->next;
            }else{
                pre->next=p->next;
                if(p->val<pivot->val) piter=phead;
                else piter=pivot;
                foundFlag=false;
                while(!foundFlag){
                    if(p->val<piter->next->val){
                        p->next=piter->next;
                        piter->next=p;
                        foundFlag=true;
                    }
                    piter=piter->next;
                }
            }
            p=pre->next;
        }
        return phead;
    } 
    

    };


Log in to reply
 

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