147. 对链表进行插入排序
1. 题目描述
对链表进行插入排序。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4
示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insertion-sort-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2.代码如下
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode node;
struct ListNode* insertionSortList(struct ListNode* head){
if (head == NULL || head->next == NULL)
{
return head;
}
node *tmphead = head;
node *ptail = head;
node *pCur = head->next;
while (pCur != NULL)
{
if (pCur->val <= tmphead->val)//若当前要进行排序的节点比有序序列中的头节点小，则直接将当前节点头插入有序序列
{
ptail->next = pCur->next;
pCur->next = tmphead;
tmphead = head = pCur;
pCur = ptail->next;
}
else
{
if (pCur->val >= ptail->val)//将当前要进行排序的节点和有序列表中的最后一个元素比较，若大于，则直接插入尾部
{
tmphead = head;
ptail = pCur;
pCur = pCur->next;
}
else//进入这里，可以确定当前节点的插入范围即不在头也不在尾，只能在有序序列中间查找到它应该插入的位置
{
while (tmphead->next != pCur)//确保是在有序序列的范围内查找
{
if (pCur->val > tmphead->next->val)
{
tmphead = tmphead->next;
}
else //得到插入位置，插入
{
ptail->next = pCur->next;
pCur->next = tmphead->next;
tmphead->next = pCur;
pCur = ptail->next;
tmphead = head;
break;
}
}
}
}
}
return head;
}