My accepted insertion sort in C++


  • 1
    P

    Brief intro: code not optimized, debugged in VC for 2 hours...ok, this is lame... But luckily one time accepted.

    ListNode *insertionSortList(ListNode *head) {
       if (head == nullptr || head->next==nullptr)
       {
          return head;
       }
       
       ListNode* t = head->next;
       ListNode* pre_t = head;
       for (; t!=nullptr;)
       {
          ListNode* a = head;
          int tval = t->val;
          int aval = a->val;
          ListNode* pre_a = t;// in case t is the smallest.
          while ((a != t) && tval > aval){
             pre_a = a;
             a = a->next;
             aval = a->val;
          }
          ListNode* u = t->next;
          if (a != t)
          {
             //in case we had to move element,
             //pre_t will not be changed for the next loop
             //because t will be u in that loop.
             pre_t->next = u;
             t->next = a;
             if (pre_a != t) 
             {
                pre_a->next = t;
             }
             else
             {// make the new smallest as head.
                head = t;
             }
    
          }
          else
          {  //in case we don't need to insert,
             //we had to prepare for the next loop
             //pre_t will be t since t will be u.
             pre_t = t;
          }
          
          t = u;
             
       }
       return head;
    }

  • 0
    K

    How about this?
    Without changing pointer just use the list like an array.

    ListNode *insertionSortList(ListNode *head) {
        ListNode *p = head;
    	if (p == NULL || p->next == NULL)
    		return p;
    	int c = 0;
    	p = p->next;
    	for (p; p != NULL; p = p->next){
    		ListNode *q = head;
    		for (q; q != p; q = q->next){
    			if (q->val > p->val){
    				c = q->val;
    				q->val = p->val;
    				p->val = c;
    			}
    		}
    	}
    	return head;
        }

  • 0
    C

    I'm afraid you implementation is not an insertion sort, pal. More like a bubble sort.


  • 0
    N

    Ha ha! You are right!


Log in to reply
 

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