目录
- 1.题目
- 2.思路
- 3.代码实现（Java）
1.题目
对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4
示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insertion-sort-list
2.思路
（1）从前往后进行插入排序，具体步骤如下：
（1.1）先判断链表是否为空，如果为空，则直接返回，否则进行下一步；
（1.2）创建插入排序需要用到的节点：
| 节点名称 | 作用 |
|---|---|
| preHead | 便于在head节点之前插入节点 |
| finalNode | 已排序部分的最后一个节点，初始值为head |
| currNode | 当前待排序节点，初始值为head.next |
（1.3）从前往后开始遍历链表（currNode为null时结束遍历）：
如果已排序部分的最后一个节点值≤当前待排序节点值，则将finalNode后移一个节点即可；
如果已排序部分的最后一个节点值>当前待排序节点值，则从链表头开始遍历，找到插入节点currNode位置的前一个节点tmpNode，并将currNode插入到tmpNode之后，下面的图片解释了对应的三行插入代码：
由于当前待排序节点已完成排序，所以将currNode向后移动一个节点
（1.4）遍历结束后，返回preHead.next即可。
3.代码实现（Java）
//（1）思路1
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
if(head==null){
return head;
}
//引入preHead:便于在head节点之前插入节点
ListNode preHead=new ListNode(0);
preHead.next=head;
//finalNode:已排序部分的最后一个节点，初始值为head
ListNode finalNode=head;
//当前待排序节点，初始值为head.next
ListNode currNode=head.next;
while(currNode!=null){
if(finalNode.val<=currNode.val){
//已排序部分的最后一个节点值≤当前待排序节点值，finalNode后移一个节点即可
finalNode=finalNode.next;
}else{
//已排序部分的最后一个节点值>当前待排序节点值
//从链表头开始遍历，tmpNode是插入节点currNode位置的前一个节点
ListNode tmpNode=preHead;
while(tmpNode.val<=currNode.val){
tmpNode=tmpNode.next;
}
//将currNode插入到tmpNode之后，具体过程可查看上面的图片
finalNode.next=currNode.next;
currNode.next=tmpNode.next;
tmpNode.next=currNode;
}
//当前待排序节点已完成排序，currNode向后移动一个节点
currNode=finalNode.next;
}
return preHead.next;
}
}