[LeetCode]Insertion Sort List

对于Array来讲，每次insert sort到index i的时候就一直和前面相邻的元素比较，看是否需要交换。LinkedList要模仿insertion sort的话需要解决一个问题，就是在当前节点是没办法和前一个节点比较的，因为单向链表的话只能从头结点开始向后遍历。但是这也给我们提供了另外一个思路，就是我们可以从头开始遍历当前元素应该插入的位置，对于每一个节点，如果其大于等于左边已经sorted部分的最大值，我们直接跳过即可因为不需要变动。对于小于左边已经sorted部分的最大值的节点，我们从head开始寻找其应该插入的部分，插入即可。时间复杂度O(N^2)，就还是insertion sort的时间复杂度，常数空间。代码如下：