C++ solution , O(n*n) time


  • 0
    W
    ListNode* insertionSortList(ListNode* head)
    {
    	if (!head)
    		return NULL;
    	ListNode *pHead = new ListNode(0);   //定义一个头结点
    	pHead->next = head;
    	head = pHead;
    
    	ListNode *curNode; //指向单链表的当前节点
    	ListNode *firstNode;
    	ListNode *secondNode;
    	ListNode *tempNode;
    
    	curNode = head->next;
    	head->next = NULL; //与原来单链表断开
    
    
    	while (curNode)
    	{
    		firstNode = head;
    		secondNode = head->next;
    
    
    		tempNode = curNode;
    		curNode = curNode->next;
    		tempNode->next = NULL;
    
    		while ((secondNode) && (secondNode->val < tempNode->val))
    		{
    			firstNode = secondNode;
    			secondNode = secondNode->next;
    		}
    		tempNode->next = secondNode;
    		firstNode->next = tempNode;
    	}
    
    	firstNode = head->next;
    	free(pHead);
    	return firstNode;
    }

Log in to reply
 

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