An intuitive solution and an optimised version in C, well-explained and commented


  • 1

    Using a head node in linked list is a common method to make it simpler to achieve conciseness and simplicity. The first intuitive solution is quite direct:

    • using a head node to collect the nodes from the original list; each time we detach a node from the original list from - from the very beginning to the end;
    • detaching a node, we have to first record its next node pointer for next round;
    • inserting it into the new list, we have to traverse it from the new head till its end; once we found a proper position (either the end of the new list or the value of the detached node is just suitable p->val>cur->val && p->val<cur->next->val);
    • we have to first let the detached node point to the next and then update the next pointer of the current node to the detached one - inserting.

    A very direct solution, just like what we normally do in insertion sort of an array

    Bang! End of Story!

    • space cost O(1)
    • time cost O(n^2)

    //AC - 68ms;
    struct ListNode* insertionSortList(struct ListNode* head)
    {
        struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
        newHead->next = NULL;
        struct ListNode *p=head, *next, *pre=newHead;
        while(p)
        {
            next = p->next;
            p->next = NULL;
            while(pre->next && pre->next->val<p->val)
                pre = pre->next;
            p->next = pre->next;
            pre->next = p;
            p = next;
            pre = newHead;
        }
        return newHead->next;
    }
    

    Actually we can do better in this inserting case

    how about we record the last pointer of the new list? each time before we traverse the new list, we test the last node first and if it's suitable to insert the original node just after the last avoiding traversing from the beginning to the end -> very time-consuming operation, then we insert it and update the last otherwise we do exactly the same as before.

    After testing, it indeed improve the performance dramatically from 64ms to 12ms almost the best submission in C 8ms.


    //AC - 12ms;
    struct ListNode* insertionSortList(struct ListNode* head)
    {
        if(!head || !head->next) return head; //we have to handle the corner case now, since we adopted last and check head->val the first round;
        struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
        newHead->next = NULL; //in case of uncertainty;
        newHead->val = head->val-1; //to update the last for the first insertion;
        struct ListNode *p=head, *next, *pre=newHead, *last=newHead;
        while(p)
        {
            next = p->next;
            p->next = NULL;
            if(last->val < p->val)
            {
                last->next = p;
                last = p;
            }
            else
            {
                while(pre->next && pre->next->val<p->val)
                    pre = pre->next;
                p->next = pre->next; //point to the next node of the current inserting position;
                pre->next = p; 
                pre = newHead; //start over from the very beginning;
            }
            p = next; //move to the next node;
        }
        return newHead->next;
    }

Log in to reply
 

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