对链表进行插入排序 图解题解
这道题到底在问什么
- 输入
- head=[4,2,1,3]
- 输出
- [1,2,3,4]
最优解：一步一步想明白
- 3记住「dummy 起手、prev 找位(prev.next.val 小于 cur.val 才前进)、改指针插入」,下面每一帧都在套它。
- 4开局:已排序链为空(只有看不见的 dummy)。读指针从原链表第一个节点 4 起,一个个取下来往已排序链里插。
- 5取出节点 4(cur),准备在左边这段已排序链 [空] 里给它找位置。先存好它的后继,免得断链丢人。
- 6prev 已经走到已排序链的尾部,链本来就空、后面没有下一个节点可比了(prev.next 为空)。停:把 cur=4 接到最后面。
- 7改指针完成插入:已排序链变成 [4]。注意全程没有搬动任何节点的数值,只是把 4 的 next 和 prev 的 next 接好。
- 8取出节点 2(cur),准备在左边这段已排序链 [4] 里给它找位置。先存好它的后继,免得断链丢人。
- 9prev 的下一个节点是 4,它不再小于 cur=2(4 ≥ 2)。停:把 cur 插到 prev 和 4 之间。
- 10改指针完成插入:已排序链变成 [2, 4]。注意全程没有搬动任何节点的数值,只是把 2 的 next 和 prev 的 next 接好。
- 11取出节点 6(cur),准备在左边这段已排序链 [2, 4] 里给它找位置。先存好它的后继,免得断链丢人。
- 12看 prev 的下一个节点 2:它比 cur=6 小,cur 要排在它后面,于是 prev 跳过 2、往后挪去看再下一个。
- 13看 prev 的下一个节点 4:它比 cur=6 小,cur 要排在它后面,于是 prev 跳过 4、往后挪去看再下一个。
- 14prev 已经走到已排序链的尾部,前面的节点都比 cur=6 小、后面没有下一个节点可比了(prev.next 为空)。停:把 cur=6 接到最后面。
- 15改指针完成插入:已排序链变成 [2, 4, 6]。注意全程没有搬动任何节点的数值,只是把 6 的 next 和 prev 的 next 接好。
- 16取出节点 1(cur),准备在左边这段已排序链 [2, 4, 6] 里给它找位置。先存好它的后继,免得断链丢人。
- 17prev 的下一个节点是 2,它不再小于 cur=1(2 ≥ 1)。停:把 cur 插到 prev 和 2 之间。
- 18改指针完成插入:已排序链变成 [1, 2, 4, 6]。注意全程没有搬动任何节点的数值,只是把 1 的 next 和 prev 的 next 接好。
- 19取出节点 3(cur),准备在左边这段已排序链 [1, 2, 4, 6] 里给它找位置。先存好它的后继,免得断链丢人。
- 20看 prev 的下一个节点 1:它比 cur=3 小,cur 要排在它后面,于是 prev 跳过 1、往后挪去看再下一个。
- 21看 prev 的下一个节点 2:它比 cur=3 小,cur 要排在它后面,于是 prev 跳过 2、往后挪去看再下一个。
- 22prev 的下一个节点是 4,它不再小于 cur=3(4 ≥ 3)。停:把 cur 插到 prev 和 4 之间。
- 23改指针完成插入:已排序链变成 [1, 2, 3, 4, 6]。注意全程没有搬动任何节点的数值,只是把 3 的 next 和 prev 的 next 接好。
- 24取出节点 5(cur),准备在左边这段已排序链 [1, 2, 3, 4, 6] 里给它找位置。先存好它的后继,免得断链丢人。
- 25看 prev 的下一个节点 1:它比 cur=5 小,cur 要排在它后面,于是 prev 跳过 1、往后挪去看再下一个。
- 26看 prev 的下一个节点 2:它比 cur=5 小,cur 要排在它后面,于是 prev 跳过 2、往后挪去看再下一个。
- 27看 prev 的下一个节点 3:它比 cur=5 小,cur 要排在它后面,于是 prev 跳过 3、往后挪去看再下一个。
- 28看 prev 的下一个节点 4:它比 cur=5 小,cur 要排在它后面,于是 prev 跳过 4、往后挪去看再下一个。
- 29prev 的下一个节点是 6,它不再小于 cur=5(6 ≥ 5)。停:把 cur 插到 prev 和 6 之间。
- 30改指针完成插入:已排序链变成 [1, 2, 3, 4, 5, 6]。注意全程没有搬动任何节点的数值,只是把 5 的 next 和 prev 的 next 接好。
- 31原链表全部取完,已排序链就是答案 [1, 2, 3, 4, 5, 6]。回头看:每取一个节点,都在已排序前缀里从头找第一个不小于它的位置插进去,dummy 让「插到最前面」也不用特判。
⚠️ 容易写错的地方
✗ 错：直接 cur = cur.next 往下走
✓ 对：先用 nxt 存住 cur.next 再断开 cur
cur 一旦被插进已排序链,它的 next 就改了,不先存后继会丢掉剩下的链
✗ 错：插到最前面时特判头节点
✓ 对：用 dummy 虚拟头统一处理
dummy 后面挂已排序链,插到最前等于插在 dummy 之后,不用单独写
✗ 错：以为 prev.next.val < 和 ≤ 没区别
✓ 对：本解用「小于」:停在第一个不小于 cur 的节点前
两种都能排对,但相等元素的相对顺序不同:用「小于」会让后来的相等节点排到先来的前面(不稳定);要稳定排序就改成「小于等于」、跳过已有的相等节点
完整代码（Python / C++ / Java）
Python
from typing import Optional, List
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0)
cur = head
while cur:
nxt = cur.next
prev = dummy
while prev.next and prev.next.val < cur.val:
prev = prev.next
cur.next = prev.next
prev.next = cur
cur = nxt
return dummy.nextC++
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
ListNode dummy(0);
while (head) {
ListNode* cur = head;
head = head->next;
ListNode* prev = &dummy;
while (prev->next && prev->next->val < cur->val) prev = prev->next;
cur->next = prev->next;
prev->next = cur;
}
return dummy.next;
}
};Java
import java.util.*;
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) {
ListNode dummy = new ListNode(0);
while (head != null) {
ListNode cur = head;
head = head.next;
ListNode prev = dummy;
while (prev.next != null && prev.next.val < cur.val) prev = prev.next;
cur.next = prev.next;
prev.next = cur;
}
return dummy.next;
}
}复杂度
时间
O(n²)
每个节点都可能从头扫一遍已排序链找位置;最坏是「已升序/每次都插到尾部」,要扫 1+2+…+n−1(完全逆序反而每次插到最前、很快)
空间
O(1)
只用 dummy、prev、cur、nxt 几个指针,原地改链不开新数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 对链表进行插入排序 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
和数组的插入排序有什么异同?+
思路一样:维护已排序前缀、逐个把新元素插到正确位置。区别在「腾位置」:数组要把后面的元素整体后移一格(O(n) 搬动),链表只需改几个 next 指针、不搬数据,所以链表插入本身是 O(1)、瓶颈只在找位置的扫描。
为什么不直接用归并排序?+
链表归并排序能做到 O(n log n),复杂度更优,实际工程里通常用它。这道题特意用插入排序,考的是链表指针插入和 dummy 哨兵这两个手法。要提醒的是:本课实现每次都从 dummy 重新扫描已排序链,并不能利用近乎有序的输入省扫描——升序输入反而是最坏情况,每个节点都要扫到链尾。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 对链表进行插入排序 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。