My accepted c++ 81ms solution, very easy understand


  • 1
    class Solution
    {
    public:
    	ListNode *insertionSortList(ListNode *head)
    	{
    		if (!head)
    		{
    			return NULL;
    		}
    		ListNode *front = head;
    		ListNode *hind = head->next;
    		front->next = NULL;
    		while (hind)
    		{
    			ListNode *now = hind;
    			hind = hind->next;
    			now->next = NULL;
    			front = merge(front, now);
    		}
    		return front;
        }
    private:
    	ListNode *merge(ListNode *front, ListNode *now)
    	{
    		if (now->val < front->val)
    		{
    			now->next = front;
    			return now;
    		}
    		ListNode *tmp = front;
    		while (tmp->next && now->val > tmp->next->val)
    		{
    			tmp = tmp->next;
    		}
    		now->next = tmp->next;
    		tmp->next = now;
    		return front;
        }
    };

Log in to reply
 

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