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     13         14     if (head==NULL||head->next==NULL)//only 0,1nodes15     {16         return    head;17     }18 19     ListNode    *pNode=head->next,*hNode=head,*tNode=NULL;20     hNode->next=NULL;21     while(pNode)22     {23         hNode=head;24 25     26 27    　　 // find where to insert28     　　while (hNode)29     　　{30         　　if (hNode->val>pNode->val)//插入头结点之前31         　　{32           　　  tNode=pNode->next;33             　　pNode->next=hNode;34             　　head=pNode;35            　　 hNode=head;36             　　pNode=tNode;37            　　 break;38         　　}39         　　else if (hNode->next==NULL)//到了最后一个节点40         　　{41             　　tNode=pNode->next;42             　　hNode->next=pNode;43            　　 pNode->next=NULL;44             　　pNode=tNode;45            　　 break;46        　　 }47        　　 else if (hNode->next->val>pNode->val)48         　　{49             　　tNode=pNode->next;50            　　 pNode->next=hNode->next;51            　　 hNode->next=pNode;52             　　pNode=tNode;53           　　  break;54        　　 }55         　　else56         　　{57            　　 hNode=hNode->next;58         　　}59         60     　　}61 62     }63     64     return head;65     }66 };