Sharing my C++ insertion sort code


  • 0
    B

    using a dummy head helps quite a lot

    class Solution {
    public:
        ListNode* insertionSortList(ListNode* head) {
            ListNode* dummy = new ListNode(INT_MIN), *cur = dummy;
            if(!head || !head->next) return head;
            dummy->next = head;
            while(cur->next) {
                if(cur->val <= cur->next->val) cur = cur->next;
                else {
                    ListNode *runner = dummy;
                    while(runner!=cur && cur->next) {
                        if(runner->next->val > cur->next->val) {
                            ListNode *temp = cur->next->next;
                            cur->next->next = runner->next;
                            runner->next = cur->next;
                            cur->next = temp;
                            break;
                        } else runner = runner->next;
                    }
                }
            }
            cur = dummy->next;
            delete dummy;
            return cur;
        }
    };
    

Log in to reply
 

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