Easy to understand C++ solution


  • 0
    K
    class Solution {
    public:
        ListNode* insertionSortList(ListNode* &head) {
            if(!head || !head->next) return head;
            ListNode* help = new ListNode(0);
            help->next = head;
            ListNode* pre = head;
            ListNode* temp = help;
    
            ListNode* cur = head->next;
            while(cur) {
                ListNode* temp1 = cur->next;
                if(cur->val >= pre->val) {
                    pre->next = cur;
                    pre = cur;
                }
                else {
                    pre->next = NULL;
                    while(temp->next->val < cur->val) {
                        temp = temp->next;
                    }
                    cout << endl;
                    ListNode* next = temp->next;
                    temp->next = cur;
                    cur->next = next;
                    temp = help;
                }
                cur = temp1;
    
            }
            return help->next;
        }
    };
    

Log in to reply
 

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