Leetcode 147. Insertion Sort List

Sort a linked list using insertion sort.

s思路： 1. insertion sort这个思路是这样的：遍历从第二个数据开始，第一个数据默认是排好序的，把第二个数据和第一个数比较插入，从而sorted的序列expanded by one, while the unsorted sequence is shrinked by one as well. 复杂度o(n^2). 2. 通常的insertion sort都是默认在vector上执行，这道题新颖的地方就是在链表上来做。也就是，当链表遇到insertion sort，会有什么事情发生？ 3. 其实可以见怪不怪的，这两个对象（链表和insertion sort）一旦被人们发现，他们之间的关系就已经当即存在，只是现在我才看到而已，本身不是什么新鲜事！ 4. 参考了以前代码，添加dummy好做一些，自己用pointer-to-pointer搞不定，搞晕了：cur代表sorted的最右边，每次用cur和cur->next比较，如果cur->val > cur->next->val,则此时就是边界，然后让PRe从dummy开始往后移动找到pre->next->val > cur->next->val,然后把cur->next这个节点插入到pre和pre->next之间。 5. 自己做的时候，尝试中规中矩的做:每次把sorted的右边界的next节点和之前的所有节点比较，找到合适的位置，然后插入。由于头节点可能改变，因此也用dummy节点；在比较的时候，也知道要找的插入的位置必须是某个指针的next，而不是某个指针之前的位置（因为链表只有next域没有pre域）。这样做的问题是，不能充分利用链表中可能存在的排好序的子链表，例如:3->2->4->1,当前两个排好序时：2->3->4->1,2和3 就不需要排序，因为是以及排好序的，所以可以节省时间！ 6. 整理一下思路：这种思路好在，每次从unsorted部分取第一个数都和sorted的最后一个数比较：如果大，则直接移动sorted的边界；如果小，才比较去找这个数应该在sorted部分的正确位置。 7. 自己为啥没想到呢？仔细观察自己的思路：默认一个新的数，直接就和sorted的部分从左往右比较了；先和右边界比较可以省事很多这点没有意识到！