Original address: https://leetcode-cn.com/problems/insertion-sort-list/description/

Title Description:

Insert and sort the linked list.

Insert sort animation as shown above. Starting with the first element, the list can be considered partially sorted (in black).
At each iteration, an element (in red) is removed from the input data and inserted in place into the ordered list.

 

Insert sort algorithm:

Insertion sorting is iterative, moving only one element at a time until all elements form an ordered output list.
In each iteration, insert sorting only removes one element to be sorted from the input data, finds its proper position in the sequence, and inserts it.
Repeat until all input data has been inserted.
 

Example 1:

Input: 4 - > 2 - > 1 - > 3
Output: 1 - > 2 - > 3 - > 4
Example 2:

Input: - 1 - > 5 - > 3 - > 4 - > 0
Output: - 1 - > 0 - > 3 - > 4 - > 5

 

Solution:

I feel that the code I wrote is OK, the time goes by, there are a lot of parameters defined, and I'm too lazy to do optimization.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if(!head || !head->next)
            return head;
        ListNode* p = head;
        ListNode* q;
        ListNode* cur;
        ListNode* pre;
        while(p->next){
            q = p->next;
            p->next = q->next;
            if(q->val < head->val){
                q->next = head;
                head = q;
                continue;
            }
            cur = head;
            pre = head;
            while(pre != p && q->val > cur->val){
                pre = cur;
                cur = cur->next;
            }
            q->next = pre->next;
            pre->next = q;
            if(pre == p)
                p = p->next;
        }
        return head;
    }
};

 

Code with the least time cost given by the official website:

Isn't this TMD fooling around???

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        vector<int> v;
        for (ListNode *p1=head;p1!=NULL;p1=p1->next){
            v.push_back(p1->val);
        }
        sort(v.begin(),v.end());
        int i=0;
        for (ListNode *p1=head;p1!=NULL;p1=p1->next){
            p1->val=v[i];
            i++;
        }
        return head;
    }
};

Another way:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (!head) return head;
        ListNode* victim=new ListNode(0);
        victim->next=head;
        ListNode* test=head->next;
        while (test)
        {
            if (test->val>=head->val)
            {
                head=head->next;
                test=head->next;
            }
            else
            {
                head->next=test->next;
                test->next=NULL;
                ListNode* dummy=victim;
                while (true)
                {
                    if (dummy->next->val<test->val)
                    {
                        dummy=dummy->next;
                    }
                    else
                    {
                        ListNode* vic=dummy->next;
                        dummy->next=test;
                        test->next=vic;
                        break;
                    }
                }
                //head=head->next;
                test=head->next;
            }
        }
        return victim->next;
    }
    
};