题目描述
给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
提示：列表中的节点数在 [1, 5000]范围内
-5000 <= Node.val <= 5000
普适的注意点
循环条件的书写顺序
比如 while(current->val>iNode->val && iNode) 这样的写法可能会出现问题，在判断current->val>iNode->val之前，应该先判断iNode是否为空，否则可能会导致访问空指针。
新节点的使用
在链表题中，如果要使用新节点应使用 new 创建，否则为临时变量，函数结束后节点将被销毁
本题要点
- 使用插入排序要明确的一个很重要的点：待排序序列分为两部分，在本轮待插入的节点前面的都是排序好的，后面都是未排序的。
- 插入时，需要处理的特殊情况：本轮待插入节点已经比排序好的序列都大，那么不用执行插入，更新待排序节点即可
- 使用假头（dummyHead）对整个链表进行统一管理，这样可以避免在排序过程中由于传入的head的位置改变而导致的错误，最后返回 dummyHead->next 即可
- 关于稳定性的要求：两处比较中使用了等于号都确保了稳定性
本题思路
/*** 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* insertionSortList(ListNode* head) {if(!head) return nullptr;ListNode *dummyHead = new ListNode(0);dummyHead->next = head;ListNode *lastSorted = head;ListNode *current = head->next;while(current){if(current->val >= lastSorted->val){//如果当前节点比已排序节点都大lastSorted = lastSorted->next;}else{ListNode *iNode = dummyHead;while(iNode->next->val<=current->val){iNode = iNode->next;}lastSorted->next = current->next;current->next = iNode->next;iNode->next = current;}current = lastSorted->next; }return dummyHead->next;}
};
- 判断链表是否为空，如果是，直接返回
- 使用假头管理链表
- 设置一个待插入节点的指针 current，用于访问待插入节点
- 设置待插入节点的前一个节点的指针 lastSorted，其实也就是排序完成的那部分的最后一个节点的指针，这个指针的作用：当 current 改变位置后，lastSorted 可以访问到下一个待插入的节点
- 一共有两个循环，对应插入排序时间复杂度为O(n^2)的特点
- 外层循环中，首先判断待插入节点是否比已排序节点都大（和最后一个排序完成的节点比较），如果是，更新最后一个排序完成的节点为当前节点，并利用最后一个排序完成的节点更新待插入节点即可
- 如果待插入节点在已排序序列中不是最大的，那么就在已排序节点中从头进行遍历，直到找到一个比待插入节点大的节点即可（此处的循环条件不用检查遍历的节点是否为空，因为第六步已经确定待插入节点比前面的已经排序完成的节点小，所以不可能遍历到链表尾，所以遍历的节点不可能为空，也就不用检查）
- 找到插入位置后，由于要将当前待插入节点进行插入，所以先要断开其原来的连接，也就是更新最后一个排序完成节点的下一个值：lastSorted->next = current->next，然后将待插入节点进行插入，最后使用最后一个排序完成的节点更新当前待插入的节点即可
