共计 1105 个字符，预计需要花费 3 分钟才能阅读完成。
题目形容
对链表进行插入排序。
从第一个元素开始，该链表能够被认为曾经局部排序（用彩色示意）。
每次迭代时，从输出数据中移除一个元素（用红色示意），并原地将其插入到已排好序的链表中。
插入排序算法：
插入排序是迭代的，每次只挪动一个元素，直到所有元素能够造成一个有序的输入列表。
每次迭代中，插入排序只从输出数据中移除一个待排序的元素，找到它在序列中适当的地位，并将其插入。
反复直到所有输出数据插入完为止。
解题思路
关键点在于了解，1、在 pre 节点前的链表都是排好序的，所以先用 pre 进行比拟，而后再从头开始比拟，这样能无效提高效率
2、减少一个头节点，这样对 head 节点的解决就能够一般化了 思路一：
1、应用游标 cur 遍历链表，直到 cur 为 null，应用 pre 节点记录主 cur 的地位，在替换完节点后将 cur 移到下一个节点
2、先和首节点比拟大小，如果小于首节点，则要进行首节点的切换（当第一第二节点雷同时，也要进行换位，否则在步骤 4 会有死循环）3、在首节点和 cur 节点之间寻找到大于 cur 节点值的节点 buf
4、将 cur 插入到 buf 前 思路二：
1、再增加个头节点 newHead，这样就缩小了个头节点的非凡解决
2、用 pre 和 cur 比照，如果 pre 小，则后移，否则，从 newHead 开始，应用下一个节点的值进行比照，找打 cur 应该在地位
3、进行移位，而后反复步骤 2 -3思路三：
就思路有点乱，效率低
1、每个数据都从头节点开始比照，应用 data 节点做遍历，2、应用 dataSlow 来保留 data 的地位，不便移位，应用 pre 保留 cur 的地位
3、对首节点要优先判断，因为他的移位比拟非凡
4、替换完节点后，将 data 节点移到第二位，dataSlow 移位到首节点（这个思路是暴力思路，没有应用头节点，导致对头节点的非凡解决，后果就是思路容易乱，第二，比照的数据不对，每次都是从头开始，如果应用和邻点比照的话，可缩小些循环；其实从代码外面就能够看到有很多反复的操作，）语言积攒
1、对于相等的状况不必理睬，在找到的第一大于的之前插入，这样就能够保障链表的稳定性
2、对于大于的状况，间接向后走就能够了
vscode 代码链接
https://github.com/lunaDolphin/leetcode/tree/master/queue_linkedList_147_1
https://github.com/lunaDolphin/leetcode/tree/master/queue_linkedList_147
https://github.com/lunaDolphin/leetcode/tree/master/queue_linkList147_2
正文完
