对链表进行插入排序（详解）
题目：
对链表进行插入排序
给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
插入排序 算法的步骤:
- 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
- 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
- 重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。
对链表进行插入排序。
示例 1：
输入: head = [4,2,1,3]
输出: [1,2,3,4]
示例 2：
输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]
提示：
- 列表中的节点数在
[1, 5000]范围内 -5000 <= Node.val <= 5000
思路：
- 首先将原链表的第一个节点head取消来当做新链表的头节点sorthead，然后让sorthead的next = NULL，让cur指向原链表的第二个节点。
（注意了，要提前判断head和head->next是否为NULL）
-
然后让cur的val去和sorthead的val去做比较，如果小于的话直接头插，大于的话就要中间插入或者尾插
-
中间插入或者尾插需要分类讨论，让sortcur指向sorthead->next，让sortprev指向sortcur得上一个节点。让sortcur去和cur做对比，如果sortcur大那就让cur插入在sortprev和sortcur之间，小的话就让sortcur继续遍历sorthead链表，当sortcur= NULL的时候，就说明cur是最大的，要尾插到链表中
-
-
最后返回sorthead
代码实现：
struct ListNode
{
int val;
struct ListNode* next;
};
typedef struct ListNode ListNode;
struct ListNode* insertionSortList(struct ListNode* head)
{
// 如果链表为空或者链表只有一个元素，那就根本不用排序
if (head == NULL || head->next == NULL)
return head;
// 创建一个新链表sorthead
// 把原链表的第一个节点取下来放到新链表
ListNode* sorthead = head;
ListNode* cur = head->next; // 让cur指向原链表第二个节点
sorthead->next = NULL;
// 然后cur遍历链表，让cur得val去和soryhead的val作对比，
// 如果cur小于sorthead，那就是头插
// 如果 cur == 或者大于的话 那就是中间插入或者尾插，
// 那就在遍历sorthead链表，让sortcur去遍历，让sortcur得val值去和cur得val值作对比
// 让sortprev指向sortcur得上一个指针
// 如果小于，就在 sortprev和sortcur之间插入
// 如果大于，那就让sortcur往后走，继续对比
// 如果出了循环，就说明cur的值最大，那就尾插到sort链表中
while (cur)
{
ListNode* next = cur->next; // next指向cur得下一个节点
// 将cur插入sort链表的同时保持有序
if (cur->val <= sorthead->val)
{
// 头插到sorthead链表
cur->next = sorthead;
sorthead = cur;
}
else // 中间插入或者尾插
{
ListNode* sortprev = sorthead; // 指向sortcur得前一个指针
ListNode* sortcur = sorthead->next;
while (sortcur)
{
if (cur->val <= sortcur->val)
{
// 中间插入
sortprev->next = cur;
cur->next = sortcur;
break;
}
else
{
// 让sortcur继续迭代，遍历链表
sortprev = sortcur;
sortcur = sortcur->next;
}
}
// 走到这里可能是cur得val值大于sorthead中的任何一个值
// 也可能是前面break出循环
// 尾插到链表
if (sortcur == NULL) // 判断是不是遍历完链表了
{
sortprev->next = cur;
cur->next = NULL;
}
}
cur = next;
}
return sorthead;
}
