Sort a linked list using insertion sort.
思路：链表的插入排序。
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
if (head == NULL || head->next == NULL)
{
return head;
}
ListNode* pNode = head->next;
ListNode* pNext;
ListNode* pre;
ListNode* unOrder = head;
ListNode* orderLast = head;
int val;
while(pNode != NULL)
{
val = pNode->val;
pNext = head;
pre = pNext;
unOrder = pNode->next;
orderLast->next = NULL;
while(pNext != NULL && val >= pNext->val)
{
pre = pNext;
pNext = pNext->next;
}
if (pre == pNext && val < pNext->val)
{
pNode->next = pre;
head = pNode;
}
else if (pre != pNext && pNext != NULL)
{
pre->next = pNode;
pNode->next = pNext;
}
else if (pre != pNext && pNext == NULL)
{
orderLast->next = pNode;
orderLast = pNode;
}
pNode = unOrder;
}
return head;
}
};