Insertion Sort List，insertionsortlist

Insertion Sort List，insertionsortlist

解題思路：
1.這個就是鏈表有序插入的變形
2.要設置4個指針，插入，查詢，插入前，查詢前指針

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     struct ListNode *next;
 6  * };
 7  */
 8 struct ListNode* insertionSortList(struct ListNode* head) {
 9     struct ListNode*  insert;
10     struct ListNode*  insert_p;         
11     struct ListNode*  cur;
12     struct ListNode*  cur_p;
13     int flag;
14     if(head == NULL)
15         return NULL;
16     insert_p = head;
17     insert = head->next;
18     while(insert != NULL){
19         cur = head;
20         cur_p = head;
21         flag = 0;
22         while(cur != insert){
23             if(head->val > insert->val){                                  //插入頭結點，要注意交換次序
24                 insert_p->next = insert->next;
25                 insert->next = head;
26                 head = insert;
27                 insert = insert_p->next;
28                 flag = 1;                 
29                 break;
30             }
31             else if(cur->val > insert->val){
32                 insert_p->next = insert->next;
33                 cur_p->next = insert;
34                 insert->next = cur;
35                 insert = insert_p->next;
36                 flag = 1;
37                 break;
38             }
39             cur_p = cur;
40             cur = cur->next;
41         }
42         if(flag == 0){                             //flag用來查看是否插入，插入的話insert已經移到下一個位置，就不用在移動了
43             insert_p = insert;
44             insert = insert->next;
45         }
46     }
47     return head;
48 }