题目
数组版插入排序的代码
受该插入排序代码启发，看题解时时刻对照该代码就很清晰啦
for (int i = 1; i < nums.length; i++) {
int temp = nums[i];
int j = i - 1;
while (j > -1 && nums[j] > temp) {
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = temp;
}
本题代码
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = head;
ListNode cur = head.next;
while (cur != null) {
if (pre.val < cur.val) {
// 此时说明不需要进行排序
pre = pre.next;
cur = cur.next;
continue;
}
// 先把 cur 节点从链表中移除
pre.next = cur.next;
// 从头开始找 cur 节点应该插入的位置
ListNode pos = dummy;
while (pos != pre && pos.next.val < cur.val) {
/* 如果 pos 的下一个值大于等于 cur 的值
此时说明找到了插入的位置
退出循环
如果 pos == pre
说明 cur 已经在正确的位置了
退出循环
*/
pos = pos.next;
}
if (pos != pre) {
// 说明需要插入
cur.next = pos.next;
pos.next = cur;
cur = pre.next;
} else {
// pos == pre 造成的退出循环
// 说明不需要插入，把移除的节点接回原位置
pre.next = cur;
pre = pre.next;
cur = pre.next;
}
}
return dummy.next;
}
}
衍生到该题的解决思路
根据插入排序的思路，我先把要插入的元素拿出来（也就是删除，由此有了pre），然后找它应该插入的位置。
初始化时，pre 相当于 i = 0 的位置，cur 是 i = 1的位置，这也可以与插入排序的代码对应起来。
插入排序的代码中，是从后往前找插入的位置，但是由于链表没法做到往前遍历（如果是双向链表，那就方便多了），所以我得从前往后找插入的位。
遍历顺序变了，所以while循环的条件语句也得变。
此时从前往后遍历，当后一个元素的节点值大于待插入元素时，就找到了该元素应该插入的位置。
又因为插入元素得拿到前一个节点的指针，然后接在它后面，所以循环条件是 pos.next.val < cur.val 当 pos.next.val >= cur.val 时退出循环
如果 pos 位置已经到了 pre 的位置，说明 cur 已经在正确的位置了，把它接回去就行
优化
如果当前元素已经在正确的位置了（也就是说它大于前一个元素的值），那么此时不用再找插入位置了（插入排序的代码因为是从后往前找，条件是 temp < nums[j - 1]，当 temp >= nums[j - 1] 时退出循环，正好就把咱们这种优化包括了）
那么当前元素大于后一个元素时，能不能说明该元素已经在正确的位置了呢？
不能，这与我们的遍历顺序有关，因为我们最外层循环是从前往后遍历，也就是说当前元素的前一个元素已经在正确的位置（前一个元素的前一个元素也在正确的位置，前一个元素的前一个元素的前一个元素。。。。），所以我们才能用它来做判断，来进行优化。这就相当于子问题被解决了，然后才能用它的结果来解决另一个子问题。
总结
-
如果是
从后往前找插入位置，排序的思路就是把当前元素插入到它的前一个元素比它小的位置，每个元素前面的元素都是小于这个元素的话，那咱们的数组自然就排好序了 -
如果是
从前往后找插入位置，排序的思路就是把当前元素插入到它的后一个元素比它大的位置，每个元素后面的元素都是大于这个元素的话，那咱们的数组自然就排好序了