My clean accepted solution in C++

  • 0

    I haven't seen clear C++ solution in the discussions, so paste my passed code. The idea is of no trick as following:

    (1) As a special case, break the 1st node from the input linkedlist as the 1st node of output linkedlist, then the head pointer of the input linkedlist is pointed to its second node,

    (2) keep breaking nodes from the remaining input linkedlist and insert this node to the correct position of the output linkedlist. The correct insert position may be at the beginning, or in the middle(end).

     ListNode * insertionSortList(ListNode * head) 
        	if (!head)
        		return NULL;
        	//first node
        	ListNode * resultHead = head;
        	head = head->next;
        	resultHead->next = NULL;
        	//remaining nodes
        	while (head)
        		ListNode * toInsert = head;
        		head = head->next;
        		if (toInsert->val < resultHead->val)  //insert to beginning
        			toInsert->next = resultHead;
        			resultHead = toInsert;
        		else  //insert to middle or end
        			ListNode * current = resultHead;
        			while ((current->next)&&(current->next->val < toInsert->val))
        				current = current->next;
        			toInsert->next = current->next;
        			current->next = toInsert;
        	return resultHead;

  • 1

    it has two lists in the processing, not sure it's pure insertion sort concept.

  • 0

    You insertion sort satisfies the O(1) space requirement but if any point in the outer while loop if you break/pause it you will essentially have 2 LLs which I think breaks the paradigm of insertion sort.

Log in to reply

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