Simple and easy-to-understand c++ code. Use an extra node before the head. It is not so fast and I don't know why.


  • 0
    L
    public:    
        ListNode* insertionSortList(ListNode* head) {
    		ListNode* p = head, *q, *pre = NULL, tmp(0);
    		tmp.next = head;
    		ListNode* prep = &tmp;
    
    		while(p){
    			for(pre=&tmp, q = tmp.next; q && q!=p && q->val < p->val; pre=q,q=q->next){
    			}
    
    			if(q == p){
    				//1 3 5  p=6;
    				// just put p in its position
    				prep = p;
    				p = p->next;
    			}
    			else{
    				//1 3 5 p=4 insert p between (3,5)
    				prep->next = prep->next->next;
    				pre->next = p;
    				p->next = q;
    				p = prep->next;
    			}
    		}
    
    		return tmp.next;
    	}

Log in to reply
 

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