My C++ 30ms solution


  • 0
    L
    class Solution{
    public:
    	ListNode* insertionSortList(ListNode* head) {
        /* 1. divide list into sorted part and unsorted part, before pointer unsorted is the sorted part
         * 2. unsorted always point to the last node of the sorted part
         * 3. sort unsorted->next to the sorted part  */
    		for (ListNode *unsorted = head; unsorted && unsorted->next; ){
    			if (unsorted->val > unsorted->next->val){
    				for (ListNode **sorted = &head; *sorted != unsorted->next; sorted = &((*sorted)->next)){
    					if ((*sorted)->val > unsorted->next->val){
    						ListNode *tmp = unsorted->next;
    						unsorted->next = tmp->next;
    						tmp->next = *sorted;
    						*sorted = tmp;
    						break;
    					}
    				}
    			}
    			else
    				unsorted = unsorted->next;
    		}
    		return head;
    	}
    };

Log in to reply
 

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