My C++ solution


  • 10
    L
    ListNode *insertionSortList(ListNode *head)
    {
    	if (head == NULL || head->next == NULL)
    		return head;
    
    	ListNode *p = head->next;
    	head->next = NULL;
    
    	while (p != NULL)
    	{
    		ListNode *pNext = p->next;    /*store the next node to be insert*/
    		ListNode *q = head;
    
    		if (p->val < q->val)    /*node p should be the new head*/
    		{
    			p->next = q;
    			head = p;
    		}
    		else 
    		{
    			while (q != NULL && q->next != NULL && q->next->val <= p->val)
    				q = q->next;
    			p->next = q->next;
    			q->next = p;
    		}
    
    		p = pNext;
    	}
    	return head;
    }

  • 0
    Z

    brilliant solution! No two star, no dummy head! Thanks for sharing!


  • 0
    C

    @lxl said in My C++ solution:

    ListNode *insertionSortList(ListNode *head)
    {
    	if (head == NULL || head->next == NULL)
    		return head;
    
    	ListNode *p = head->next;
    	head->next = NULL;
    
    	while (p != NULL)
    	{
    
                //all these no see ???
    
    		ListNode *pNext = p->next;    /*store the next node to be insert*/
    		ListNode *q = head;
    
    		if (p->val < q->val)    /*node p should be the new head*/
    		{
    			p->next = q;
    			head = p;
    		}
    		else 
    		{
    			while (q != NULL && q->next != NULL && q->next->val <= p->val)
    				q = q->next;
    			p->next = q->next;
    			q->next = p;
    		}
    
    		p = pNext;
    	}
    	return head;
    }

Log in to reply
 

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