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 *left=NULL,*right=head;
13         if(head==NULL)
14             return head;
15         left=head;
16         right=head->next;
17         left->next=NULL;
18         
19         while(right!=NULL){
20             ListNode *p=left;
21             ListNode *cur=right;
22             
23             while(p!=NULL&&p->next!=NULL&&p->next->val<right->val)
24                 p=p->next;
25             right=right->next;
26             if(p->val<=cur->val){
27                 cur->next=p->next;
28                 p->next=cur;
29             }else{
30                 cur->next=p;
31                 left=cur;
32             }
33             
34             
35         }
36         return left;
37     }
38 };