关于java:链表插入排序leetcode147

题目形容

对链表进行插入排序。
从第一个元素开始，该链表能够被认为曾经局部排序（用彩色示意）。
每次迭代时，从输出数据中移除一个元素（用红色示意），并原地将其插入到已排好序的链表中。

插入排序算法：

插入排序是迭代的，每次只挪动一个元素，直到所有元素能够造成一个有序的输入列表。
每次迭代中，插入排序只从输出数据中移除一个待排序的元素，找到它在序列中适当的地位，并将其插入。
反复直到所有输出数据插入完为止。

解题思路

关键点在于了解，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