4
leetCode解题报告之Insertion Sort List
source link: https://blog.csdn.net/ljphhj/article/details/21200455
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
leetCode解题报告之Insertion Sort List_快乐de胖虎-CSDN博客
题目：
Sort a linked list using insertion sort.
分析：
这个题目是想要让我们来做一个链表的插入排序问题.
这样，我们只要从第一个元素一直往后，直到所有的节点都在前面的序列中找到自己所在的位置即可
情况：
1. 当前值比head的值还小，这情况要插入到head节点之前
2. 当前值比head的值大，这情况要插入到相应的位置
3. 当前值大于所有该节点之前的值，那么当cmpNode(用来作比较的结点)和自身相等的时候，只要将当前结点(nowNode)往后挪一个结点进行下一个结点的比较即可.
解题思路：
大家都知道，如果要在一个位置插入一个结点，那么要知道它的前一个位置的结点才可以，所以为了满足“情况1”，我们引入一个结点preHead(head的前一个结点)，它的next域指向head。
接着引入一个 nowNode(当前结点) 和 一个 preNowNode（当前结点的前驱结点）【处于nowNode之前的那些结点是已经排好序了】
最后在引入一个cmpNode(做比较的结点) 和一个preCmpNode(正在做比较的结点的前驱结点) 【从head 直到 nowNode ，依次取出来 和 nowNode做比较，确定nowNode要插入的位置】
有了上面的这些介绍，剩下的看代码，应该就容易多了！！
附个过程图解：
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK