Insertion Sort List

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* insertionSortList(ListNode* head) {
12         ListNode * temp=head;  //用于最外层循环的控制。表述的是当前节点
13         ListNode * tail;  
14         ListNode * myhead=NULL;
15         if(head==NULL)
16             return NULL;
17         while(temp!=NULL)
18         {
19             tail=temp->next;
20             myhead=insertNode(myhead,temp);
21             temp=tail;
22         }
23         return myhead;
24     }
25     ListNode * insertNode(ListNode * head,ListNode * temp)
26     {
27         temp->next=NULL;
28         if(head==NULL)
29             return temp;
30         ListNode * t=head;
31         ListNode * pre=NULL;
32         while(t!=NULL)
33         {
34             if((temp->val)<(t->val))
35             {
36                 if(pre!=NULL)
37                 {
38                     pre->next=temp;
39                 }
40                 temp->next=t;
41                 break;
42             }
43             pre=t;
44             t=t->next;
45             if(pre->next==NULL)
46                 pre->next=temp;
47                 
48             
49         }
50         if(pre==NULL)
51             head=temp;
52         return head;
53     }
54 };