Explained C++ solution (24ms)


  • 46

    Well, life gets difficult pretty soon whenever the same operation on array is transferred to linked list.

    First, a quick recap of insertion sort:

    Start from the second element (simply a[1] in array and the annoying head -> next -> val in linked list), each time when we see a node with val smaller than its previous node, we scan from the head and find the position that the current node should be inserted. Since a node may be inserted before head, we create a new_head that points to head. The insertion operation, however, is a little easier for linked list.

    Now comes the code:

    class Solution { 
    public:
        ListNode* insertionSortList(ListNode* head) {
            ListNode* new_head = new ListNode(0);
            new_head -> next = head;
            ListNode* pre = new_head;
            ListNode* cur = head;
            while (cur) {
                if (cur -> next && cur -> next -> val < cur -> val) {
                    while (pre -> next && pre -> next -> val < cur -> next -> val)
                        pre = pre -> next;
                    /* Insert cur -> next after pre.*/
                    ListNode* temp = pre -> next;
                    pre -> next = cur -> next;
                    cur -> next = cur -> next -> next;
                    pre -> next -> next = temp;
                    /* Move pre back to new_head. */
                    pre = new_head;
                }
                else cur = cur -> next;
            }
            ListNode* res = new_head -> next;
            delete new_head;
            return res;
        }
    };

  • 0
    V

    Nice solution! Thanks for sharing!


  • 1

    You are very welcome.


  • 0
    J

    I thought the list had a header pointer.....but it does not......

    And you add the header node, so it's more easy to handle.

    Thanks for your sharing!

    btw, you didn't delete the temporary node new_head .


  • 0

    Hi, justyu. Thank you for your remind. I have updated my code :-)


  • 0
    H
    This post is deleted!

  • 0
    L

    I can't figure out why the code below has runtime error , does anyone have any idea?

    class Solution {
    public:

    ListNode* insertionSortList(ListNode* head) {
        ListNode* newHead=new ListNode(0);
        newHead->next=head;
        ListNode* pre=newHead;
        ListNode* cur=head;
        while(cur){
            if(cur->next&&cur->next->val<cur->val){
                while(pre->next&&pre->next->val<cur->next->val)
                    pre=pre->next;
                ListNode* temp=cur->next;
                cur->next=cur->next->next;
                cur->next->next=pre->next;
                pre->next=temp;
                pre=newHead;
            }
            else cur=cur->next;
        }
        return newHead->next;
    }
    

    };


  • 0

    Your code meets runtime error in the case 2 -> 1 -> NULL. If you run it by hand, you will see that after running cur -> next = cur -> next -> next, cur -> next becomes NULL. But then you execute cur -> next -> next = pre -> next, which is like NULL -> next = pre -> next and thus gives the runtime error.


  • 0
    L

    yes,it is,thank you


  • 0
    O

    Thanks for sharing man, I borrow your idea and change to Python, but it's still not fast enough QQ. But still, your explanation are really clear!


  • 0
    D

    Is this O(n^2) in time? I don't see any binary search process here.


  • 1
    Y

    A minor change.
    Dynamic memory allocation is in general more expensive, here use a local dummy node instead of head allocated node.

    class Solution {
    public:
        ListNode* insertionSortList(ListNode* head) {
            ListNode dummy(INT_MIN),*pre(&dummy),*next(nullptr);
            dummy.next = head;
            while(head){
                pre = &dummy;
                if(head && head->next && head->val > head->next->val){
                    while(pre && pre->next && pre->next->val < head->next->val){
                        pre = pre->next;
                    }
                    next = pre -> next;
                    pre -> next = head -> next;
                    head -> next = head -> next -> next;
                    pre -> next -> next = next;
                } else {
                    head = head->next;
                }
            }
            return dummy.next;
        }
    };
    

  • 0
    S

    Perfect! Thank you!


  • 0

    My code based on your method:

    
    ListNode* insertionSortList(ListNode* head)
    {
    	if (!head || !head->next)
    		return head;
    	ListNode **curr = &head->next;
    	ListNode **p = nullptr;
    	int pre = head->val;
    	while(*curr)
    	{
    		if ((*curr)->val < pre)
    		{
    			for (p = &head; (*curr)->val >= (*p)->val; p = &(*p)->next);
    			swap((*curr)->next, *p);
    			swap(*p, *curr);
    
    		}
    		else
    		{
    			pre = (*curr)->val;
    			curr = &(*curr)->next;
    		}
    	}
    	return head;
    }
    

  • 0
    9
    cur -> next = cur -> next -> next;
    pre -> next -> next = temp;
    

    if i interchange the order of the above 2 lines I get TLE. What am I missing to see?


Log in to reply
 

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