My C++ solution


  • 2
    public:
        ListNode* insertionSortList(ListNode* head) {
            if (!head || !head->next) return head;
    		ListNode* front = new ListNode(0);
    		front->next = head;
    		head = front;                            // insert head node
    		ListNode* pos = head->next;
    		while (pos->next){
    			ListNode* prev = pos->next;
    			if (prev->val < pos->val){
    				ListNode* loop_pos = head;
    				while (prev->val >= loop_pos->next->val) loop_pos = loop_pos->next;
    				pos->next = prev->next;
    				prev->next = loop_pos->next;
    				loop_pos->next = prev;
    				continue;
    			}
    			pos = prev;
    		}
    		return front->next;
        }
    };

Log in to reply
 

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