Accepted insertion sort list


  • 2
    N
    class Solution {
    public:
        ListNode *insertionSortList(ListNode *head) {
            
        if(!head) return NULL;
    	
    	// add new node with INT_MIN
    	ListNode* newHead = new ListNode(INT_MIN);
    	newHead->next = head;
    
    	// loop every node
    	for(ListNode*p = head->next, *prep = head; p; prep = p, p=p->next)
    	{
    	    // insert them to the right position of link list
    		for(ListNode * cur = newHead; cur->next!=p; cur = cur->next)
    		{
    			if (cur->next->val > p->val)
    			{
    				// insert between cur * cur->next
    				prep->next = p->next;
    				p->next = cur->next;
    				cur->next = p;
    				p = prep;
    				break;
    			}
    		}
    	}
    	ListNode* result = newHead->next;
    	delete newHead;
    	return result;
        }
    };

  • -3
    J

    I think the following solution is better without using new nodes:

    class Solution {
    public:
    ListNode *insertionSortList(ListNode *head) {
        if(head==NULL || head->next==NULL) return head;
        ListNode *cur = head;
        while(cur) {
            ListNode *tmp = cur->next;
            while(tmp) {
                if(tmp->val < cur->val) {
                    int a = tmp->val;
                    tmp->val = cur->val;
                    cur->val = a;
                }
                tmp = tmp->next;
            }
            cur = cur->next;
        }
        return head;
    }
    };

  • 0
    X

    I don't think your sol is better than Nepheline's,even your code is simplify than his,but for the interview ,you need to kown how two swap two node。I think change the node is much better than change the val.


  • 0
    H

    definition for prep is missing


  • 0
    T

    this is not insertion sorting....


  • 0
    X

    +1, not insertion sort, feels like bubble sort...


  • 0
    N
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 0
    P

    not insertion sorting....you have to read this question again....


Log in to reply
 

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