排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
选择插入排序算法：
插入排序算法的原理是让锚点前面的数值都有序，每次都从锚点之后找到一个值往前插入。
分为两步：
- 1 遍历链表
- 2 从链表中找到合适的插入位置
一些小细节，先去原始链表中找到一个节点，然后从dummy节点开始找到适合插入的位置原始链表少一个几点，dummy链表多一个节点）：
- 1 遍历链表是从head开始
- 2 在从链表中找到合适的插入位置之前需要保存好cur的下一个位置，用于更新遍历链表
- 3 从链表中找到合适的插入位置是从dummy节点开始。
- 4 链表的插入需要先顾尾后顾头
- 5 链表的循环从head开始，到最后一个节点结束.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
ListNode* dummy = new ListNode(0);
ListNode* cur = head;
while(cur){
ListNode* in_cur = dummy;
ListNode* next_node = cur->next;
while(in_cur->next && in_cur->next->val <= cur->val){
in_cur = in_cur->next;
}
cur->next = in_cur->next;
in_cur->next = cur;
cur = next_node;
}
return dummy->next;
}
};