# [LeetCode] 147. Insert and sort the linked list and finish the report (C + +)

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:

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* q;
ListNode* cur;
ListNode* pre;
while(p->next){
q = p->next;
p->next = q->next;
continue;
}
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;
}
}
};```

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

Isn't this TMD fooling around???

```class Solution {
public:
vector<int> v;
v.push_back(p1->val);
}
sort(v.begin(),v.end());
int i=0;
p1->val=v[i];
i++;
}
}
};```

Another way:

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* victim=new ListNode(0);
while (test)
{
{
}
else
{
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;
}
}