友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
147. 对链表进行插入排序
给定单个链表的头 head，使用 插入排序 对链表进行排序，并返回 排序后链表的头。
插入排序 算法的步骤:
-
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
-
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
-
重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。
对链表进行插入排序。
示例 1：
输入: head = [4,2,1,3] 输出: [1,2,3,4]
示例 2：
输入: head = [-1,5,3,4,0] 输出: [-1,0,3,4,5]
提示：
-
列表中的节点数在 `[1, 5000]`范围内
-
-5000 <= Node.val <= 5000
思路分析
首先建立虚拟头节点（头结点的值要足够小），然后从头节点向后遍历，遇到当前值比前一个节点值小，则把这个值摘出来，从头结点向后寻找插入位置。
另外，只有在当前节点比前一个节点大时才需要向后移动当前节点。当大小相反时，因为把当前节点摘出来了，前一个节点的下一个节点的值已经发生了变化。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-06-26 21:56:34
*/
public ListNode insertionSortList(ListNode head) {
ListNode dummy = new ListNode(Integer.MIN_VALUE);
dummy.next = head;
ListNode prev = dummy;
while (prev.next != null) {
ListNode curr = prev.next;
if (curr.val < prev.val) {
prev.next = curr.next;
ListNode first = dummy;
while (first.next.val < curr.val) {
first = first.next;
}
curr.next = first.next;
first.next = curr;
} else {
prev = prev.next;
}
}
return dummy.next;
}