C++ solution, 87 ms


  • 0
    X
    class Solution
    {
    public:
    	ListNode* insertionSortList(ListNode* head)
    	{
    	    if(NULL == head || NULL == head->next)
    	        return head;
    		ListNode* p = new ListNode(INT_MIN);
    		p->next = head;
    		head = p;
    		p = head->next;
    		while(NULL!= p->next)
    		{
    			ListNode* temp = p->next;
    			p->next = temp->next;
    			temp->next = NULL;
    
    			ListNode* cursor = head;
    			while(p != cursor && temp->val > cursor->next->val)
    			{
    				cursor = cursor->next;
    			}
    
    			if(p == cursor)
    			{
    				temp->next = cursor->next;
    				cursor->next = temp;
    				p = temp;
    			}
    			else
    			{
    				temp->next = cursor->next;
    				cursor->next = temp;
    			}
    		}
    		return head->next;
    	}
    };

Log in to reply
 

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