题目：Sort a linked list using insertion sort.
代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *insertionSortList(ListNode *head) { if (head==NULL||head->next==NULL)//only 0,1nodes
{
return head;
} ListNode *pNode=head->next,*hNode=head,*tNode=NULL;
hNode->next=NULL;
while(pNode)
{
hNode=head; // find where to insert
while (hNode)
{
if (hNode->val>pNode->val)//插入头结点之前
{
tNode=pNode->next;
pNode->next=hNode;
head=pNode;
hNode=head;
pNode=tNode;
break;
}
else if (hNode->next==NULL)//到了最后一个节点
{
tNode=pNode->next;
hNode->next=pNode;
pNode->next=NULL;
pNode=tNode;
break;
}
else if (hNode->next->val>pNode->val)
{
tNode=pNode->next;
pNode->next=hNode->next;
hNode->next=pNode;
pNode=tNode;
break;
}
else
{
hNode=hNode->next;
} } } return head;
}
};