题目描述
思路解析动画文字版
记住「dummy 起手、prev 找位(prev.next.val 小于 cur.val 才前进)、改指针插入」,下面每一帧都在套它。
开局:已排序链为空(只有看不见的 dummy)。读指针从原链表第一个节点 4 起,一个个取下来往已排序链里插。
取出节点 4(cur),准备在左边这段已排序链 [空] 里给它找位置。先存好它的后继,免得断链丢人。
prev 已经走到已排序链的尾部,链本来就空、后面没有下一个节点可比了(prev.next 为空)。停:把 cur=4 接到最后面。
改指针完成插入:已排序链变成 [4]。注意全程没有搬动任何节点的数值,只是把 4 的 next 和 prev 的 next 接好。
取出节点 2(cur),准备在左边这段已排序链 [4] 里给它找位置。先存好它的后继,免得断链丢人。
prev 的下一个节点是 4,它不再小于 cur=2(4 ≥ 2)。停:把 cur 插到 prev 和 4 之间。
改指针完成插入:已排序链变成 [2, 4]。注意全程没有搬动任何节点的数值,只是把 2 的 next 和 prev 的 next 接好。
取出节点 6(cur),准备在左边这段已排序链 [2, 4] 里给它找位置。先存好它的后继,免得断链丢人。
看 prev 的下一个节点 2:它比 cur=6 小,cur 要排在它后面,于是 prev 跳过 2、往后挪去看再下一个。
看 prev 的下一个节点 4:它比 cur=6 小,cur 要排在它后面,于是 prev 跳过 4、往后挪去看再下一个。
prev 已经走到已排序链的尾部,前面的节点都比 cur=6 小、后面没有下一个节点可比了(prev.next 为空)。停:把 cur=6 接到最后面。
改指针完成插入:已排序链变成 [2, 4, 6]。注意全程没有搬动任何节点的数值,只是把 6 的 next 和 prev 的 next 接好。
取出节点 1(cur),准备在左边这段已排序链 [2, 4, 6] 里给它找位置。先存好它的后继,免得断链丢人。
prev 的下一个节点是 2,它不再小于 cur=1(2 ≥ 1)。停:把 cur 插到 prev 和 2 之间。
改指针完成插入:已排序链变成 [1, 2, 4, 6]。注意全程没有搬动任何节点的数值,只是把 1 的 next 和 prev 的 next 接好。
取出节点 3(cur),准备在左边这段已排序链 [1, 2, 4, 6] 里给它找位置。先存好它的后继,免得断链丢人。
看 prev 的下一个节点 1:它比 cur=3 小,cur 要排在它后面,于是 prev 跳过 1、往后挪去看再下一个。
看 prev 的下一个节点 2:它比 cur=3 小,cur 要排在它后面,于是 prev 跳过 2、往后挪去看再下一个。
prev 的下一个节点是 4,它不再小于 cur=3(4 ≥ 3)。停:把 cur 插到 prev 和 4 之间。
改指针完成插入:已排序链变成 [1, 2, 3, 4, 6]。注意全程没有搬动任何节点的数值,只是把 3 的 next 和 prev 的 next 接好。
取出节点 5(cur),准备在左边这段已排序链 [1, 2, 3, 4, 6] 里给它找位置。先存好它的后继,免得断链丢人。
看 prev 的下一个节点 1:它比 cur=5 小,cur 要排在它后面,于是 prev 跳过 1、往后挪去看再下一个。
看 prev 的下一个节点 2:它比 cur=5 小,cur 要排在它后面,于是 prev 跳过 2、往后挪去看再下一个。
看 prev 的下一个节点 3:它比 cur=5 小,cur 要排在它后面,于是 prev 跳过 3、往后挪去看再下一个。
看 prev 的下一个节点 4:它比 cur=5 小,cur 要排在它后面,于是 prev 跳过 4、往后挪去看再下一个。
prev 的下一个节点是 6,它不再小于 cur=5(6 ≥ 5)。停:把 cur 插到 prev 和 6 之间。
改指针完成插入:已排序链变成 [1, 2, 3, 4, 5, 6]。注意全程没有搬动任何节点的数值,只是把 5 的 next 和 prev 的 next 接好。
原链表全部取完,已排序链就是答案 [1, 2, 3, 4, 5, 6]。回头看:每取一个节点,都在已排序前缀里从头找第一个不小于它的位置插进去,dummy 让「插到最前面」也不用特判。
边界:空/单节点直接返回;已升序是最坏(每次扫到尾)、完全逆序反而最快(每次插最前)。
两个高频追问:对比数组插入排序(链表免搬动)、对比归并排序(更优但本题考指针)。
参考代码
from typing import Optional, Listclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass 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.next复杂度
- 时间：O(n²)，每个节点都可能从头扫一遍已排序链找位置;最坏是「已升序/每次都插到尾部」,要扫 1+2+…+n−1(完全逆序反而每次插到最前、很快)
- 空间：O(1)，只用 dummy、prev、cur、nxt 几个指针,原地改链不开新数组
易错点
面试追问把动画讲成自己的话
追问和数组的插入排序有什么异同?
追问为什么不直接用归并排序?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
排序链表
LeetCode 148 · 中等 · 沿着 链表套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题