如果你在搜索引擎里搜“LeetCode 82 378 373 链表”大概率会看到一堆互相独立的题解。我第一次把这三道题放在一起刷的时候也愣了一下——82是删除排序链表中的重复元素标准链表题378是有序矩阵中第K小矩阵题373是找出和最小的K对数字数组题。这几题放一起乍看像是标题党。但刷完回头看它们其实共用一套底层思维都是在一个或多个有序序列上线性推进谁能快速找到“下一个最小的元素”谁就能拿到答案。只不过82题不用堆用指针378和373用堆来模拟多路指针。这篇文章我把三题串起来讲重点不是背代码而是把这种“有序序列归并”的思维方式讲透。适合正在集中刷LeetCode链表专题、或者准备面试前想找共性规律的朋友。1. 先花两分钟想清楚这三道题为什么会被归到“链表题”里1.1 我的判题习惯先看数据范围再选解法我刷题有个习惯拿到一道题不急着想模板先看数据和约束。链表题最重要的是节点数量如果链表几千个节点递归爆不了栈如果上十万递归就可能栈溢出。LeetCode 82题节点数通常不大迭代和递归都能过但我还是建议用迭代因为在真实工程里递归处理链表很容易在大链表上踩栈溢出的坑。378和373更明显。378矩阵大小n最大到300值域却可能很大373的nums1和nums2长度最多10万k可能只有几百。数据范围不一样同一个“找前K个”问题的解法倾向就完全不同。先看范围再选解法比直接背模板可靠得多。把这三题放一起其实是个很好的练习先接收输入冷静判断“这是不是一个有序序列问题”再决定用指针线性扫描还是用堆做K路归并还是值域二分。这比只记住某一道题的代码重要得多。1.2 有序序列是“无形的链表”很多人觉得链表就是next指针串起来的东西其实链表最本质的特征是每个节点只知道下一个节点是谁而且整个序列有序。有序数组和有序列也具备这个性质——沿着下标方向值单调不减。如果把“取下一个元素”这个动作抽象出来你就会发现数组、矩阵、链表没有本质区别。378题矩阵的每一行都是有序的373题nums1和nums2都是有序的所以它们都能被改造成多条“有序链表”。这正是经典“合并K个有序链表”的变形。K路归并是链表题里非常常见的一个分支373题几乎就是“合并K个有序链表”的换皮。我建议你刷题时养成一个习惯每道题先问自己这里有几个有序序列每个序列怎么前进这才是把题解真正变成自己能力的关键。2. 82题dummy节点是链表去重的护城河2.1 先看懂题不是“去重保留一个”是“重复的全扔掉”LeetCode 82题题目是给定一个已排序的链表删除所有重复数字的节点只留下原始链表中没有重复出现的数字。注意区别LeetCode 83题是“删除重复元素每个数字保留一个”82题是“所有重复元素全部删除”。比如链表是1-2-3-3-4-4-583题返回1-2-3-4-582题返回1-2-5。很多初学者一看到deleteDuplicates这个函数名下意识就写成83题那种保留了。这题真正难的点是如果头节点就是重复的整个头要换如果重复段很长要一次性跳过整段。所以需要一个哑节点来兜底。2.2 代码cur从dummy出发一次看两个节点直接上C代码class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if (!head || !head-next) return head; ListNode dummy(0); dummy.next head; ListNode* cur dummy; while (cur-next cur-next-next) { if (cur-next-val cur-next-next-val) { int val cur-next-val; while (cur-next cur-next-val val) { ListNode* tmp cur-next; cur-next cur-next-next; delete tmp; } } else { cur cur-next; } } return dummy.next; } };核心逻辑是cur始终指向“已经确认安全”的节点然后看它后面的两个节点cur-next和cur-next-next。如果这两个值相等说明从cur-next开始是一段重复节点记下这个值val然后不断把cur-next删掉直到下一个节点的值不等于val。如果两个值不等说明cur-next可以安全收下cur前移一位。这里有个常见的误区有人会先删一个再回头判断结果删不干净或者被悬垂指针搞懵。正确做法是先用while把整段重复的节点全部跳过再移动cur。2.3 为什么不用哈希表统计一遍有些同学看到“删除所有重复数字”第一反应是哈希表统计每个值出现的次数然后再遍历一遍删掉。这个思路没错但在这道题里是绕了远路。链表是已排序的重复元素一定排在一起。既然排在一起就不需要统计全局次数只需要判断“当前节点和下一个节点是否相等”就够了。用哈希表的话第一遍遍历要O(n)额外空间存次数第二遍还要遍历删节点而看两个节点的方法空间O(1)时间O(n)一遍搞定。这也反映了一个很重要的刷题观数据结构的有序性本身就是信息。排序链表能提供“相邻相等即重复”这个性质就应该利用起来而不是把有序性扔到一边退回最通用的哈希表方案。2.4 四个容易翻车的边界我实际提交时第一次就挂在边界上。这里给你列全空链表和单节点链表直接返回head后面的while循环会空指针报错所以开头必须判掉。头节点开始连续重复比如1-1-1-2-3。如果没有dummy节点返回逻辑会非常别扭。dummy节点在这里的价值就体现出来了头节点也可以像普通节点一样被“跳过”最后返回dummy.next就是新头。尾部重复比如1-2-3-3-3。内层while循环里必须写cur-next非空判断否则当cur-next移到nullptr时取cur-next-val会崩。全部重复比如1-1-1。最后dummy.next变成nullptr返回空链表。这个场景很多人会漏测建议本地跑一下。另外C里用delete释放被删除的节点LeetCode的内存检查对这点不严格但本地调试时养成delete的习惯是好事。Java、C#这类有GC的语言不需要这步写起来更轻松。3. 378题每一行都是一条有序链表3.1 矩阵的单调性如何变成“链表”378题给定一个n x n矩阵每行和每列都按升序排列要求找第k小的元素。这个矩阵最妙的地方在于每行有序每列也有序。这意味着如果只看每一行它完全就是一条有序链表——第一列的元素是链表的头沿着行方向下一个元素就是“后继”。于是整个矩阵就变成了n条有序链表的集合。目标“找第k小的元素”等价于从这n条有序链表中做K路归并取第k个弹出的元素。这个视角一旦建立解题思路就非常清晰了用一个大小为n的小顶堆堆里存每条链表的当前节点。每次弹出最小的节点然后把该行下一个节点入堆。重复k次堆顶就是第k小的元素。3.2 解法A优先队列模拟K路归并代码实现如下struct Node { int val; int row; int col; bool operator(const Node other) const { return val other.val; } }; class Solution { public: int kthSmallest(vectorvectorint matrix, int k) { int n matrix.size(); priority_queueNode, vectorNode, greaterNode pq; for (int r 0; r n; r) { pq.push({matrix[r][0], r, 0}); } for (int step 1; step k; step) { Node top pq.top(); pq.pop(); int r top.row; int c top.col; if (c 1 n) { pq.push({matrix[r][c 1], r, c 1}); } } return pq.top().val; } };Node里存了三个信息值、行、列。为什么要存行列因为弹出某个节点的值之后我需要知道这个值是从第几行第几列来的才能找到该行下一个节点。如果不存行列弹出后就不知道后继是谁了。这个流程可以类比成有n张按顺序排好的扑克牌堆每次抽所有牌堆顶中最小的一张再翻它后面一张。第k次抽到的牌就是第k小的元素。时间复杂度O(k log n)空间O(n)。当k比较小的时候这个解法非常舒服。但如果k接近n²那就要考虑第二种思路了。3.3 解法B值域二分适用于k接近n²的情况当k很大时堆解法会退化到O(n² log n)这时候值域二分就更有优势。思路是矩阵里最小元素是matrix[0][0]最大是matrix[n-1][n-1]答案一定在这个值域区间里。二分这个值mid统计矩阵里有多少个元素小于等于mid。如果数量大于等于k说明第k小的数不超过mid把右边界收紧否则说明答案比mid大把左边界调高。统计数量时因为每行都是有序的可以直接用upper_bound找到mid在每行的插入位置累加即可。class Solution { public: int kthSmallest(vectorvectorint matrix, int k) { int n matrix.size(); int left matrix[0][0]; int right matrix[n - 1][n - 1]; while (left right) { int mid left (right - left) / 2; int count 0; for (int i 0; i n; i) { count upper_bound(matrix[i].begin(), matrix[i].end(), mid) - matrix[i].begin(); } if (count k) { right mid; } else { left mid 1; } } return left; } };有一个关键点需要想清楚二分出来的最终答案一定在矩阵中。因为当循环结束时left是满足“小于等于left的元素至少k个”的最小值。如果left不在矩阵中那么小于等于left-1的元素数量和小于等于left的数量完全一样也会满足至少有k个这跟“最小”矛盾。所以最终left一定是某个矩阵元素。这里还要提醒一个细节统计时不能用lower_bound必须用upper_bound。lower_bound返回的是第一个大于等于mid的位置等于mid的元素不会被计入导致统计数量偏小。我要的是“小于等于mid的个数”所以必须用upper_bound。这个坑我踩过一次查了半天才发现统计口径不对。自然值域二分的复杂度是O(n log(max-min))空间O(1)。当n不大但值域很大时特别稳。3.4 怎么选一张表说清楚维度堆解法值域二分核心思想K路归并二分答案值域时间复杂度O(k log n)O(n log(max-min))空间复杂度O(n)O(1)适用场景k较小k接近n²或值域较大代码难度中等需自定义结构体中等需理解计数条件典型坑列越界、堆比较方向lower_bound和upper_bound用错我的建议是只要矩阵规模不太大先考虑堆解法逻辑直观不容易写错遇到k很大或者明确要求空间O(1)的场合再切值域二分。这两套解法最好都练熟面试时经常会被追问第二种。4. 373题看起来只和数组有关解法却是链表的“薪火相传”4.1 把一个二维配对问题改写成一堆有序链表先看题目给定两个升序数组nums1和nums2找到和最小的k个数对。数对由nums1中的一个数和nums2中的一个数组成。这题第一眼是个组合问题暴力枚举所有数对至少O(mn)肯定不行。但如果你把每个nums1[i]固定下来让nums2的下标j从0递增那么序列nums1[i]nums2[0]、nums1[i]nums2[1]、nums1[i]nums2[2]...是单调不减的。这不就是一条有序链表吗每条链表的头节点是nums1[i]nums2[0]后继节点就是把nums2下标加一。于是问题完全变成了合并m条有序链表取前k个元素。这不是链表题是什么4.2 代码堆里只存下标值当场算实现如下class Solution { public: vectorvectorint kSmallestPairs(vectorint nums1, vectorint nums2, int k) { vectorvectorint res; int m nums1.size(); int n nums2.size(); if (m 0 || n 0 || k 0) return res; auto cmp [](const pairint, int a, const pairint, int b) { return nums1[a.first] nums2[a.second] nums1[b.first] nums2[b.second]; }; priority_queuepairint, int, vectorpairint, int, decltype(cmp) pq(cmp); for (int i 0; i min(k, m); i) { pq.push({i, 0}); } while (!pq.empty() (int)res.size() k) { auto top pq.top(); pq.pop(); int i top.first; int j top.second; res.push_back({nums1[i], nums2[j]}); if (j 1 n) { pq.push({i, j 1}); } } return res; } };注意代码里堆中每个元素只存了nums1的下标i和nums2的下标j真正的和是每次比较时当场算出来的。这样做的好处是节省空间不需要把和值单独存一份。还有个关键设计每条链表只往j1方向推进。这意味着同一个数对只会从一个链头进入堆不会重复入堆所以不需要像某些写法那样维护visited二维数组。如果你看到网上有加visited的版本那是采用了“从(0,0)同时向右和向下扩展”的模型我这里用的是“固定nums1为链头单方向推进”的模型更接近归并有序链表的本质也更简洁。4.3 优化只推前min(k, m)个链头而且安全你可能注意到初始化时我只把前min(k, m)个链头放进了堆。这是有讲究的。第i条链表的最小元素是nums1[i]nums2[0]。因为nums1是升序的所以链头值随着i递增。如果m大于k那么第k条以后的链表其最小元素都不会小于前k个链头中的任何一个。换句话说前k小的数对一定只可能来自前k条链表后面的行头连进入前k的资格都没有。这里要严谨一点即使存在并列相等的情况数对集合也不会受影响。因为我们要的是集合不是下标前k个候选已经能保证覆盖所有可能的和值。如果不用这个优化直接把m个头全部入堆代码也能过但初始堆就要O(m)的构建时间。当m是10万级别而k只有100时这个优化能明显减少无用功。另外还有一个优化方向如果nums2长度比nums1短很多可以考虑固定nums2为链头让堆的大小由较短的数组决定。核心思想是“选短的当链头减少堆顶候选数”。4.4 时空复杂度堆中同一时刻最多只有min(k, m)个元素因为每条链表在同一时刻只会贡献一个节点。所以空间复杂度O(min(k, m))。每个元素进出堆一次每次堆操作O(log(min(k, m)))总共k个元素要pop出来时间复杂度O(k log(min(k, m)))。这个复杂度在m、n都很大的场景下也非常能打。5. 三道题串起来多路归并与指针状态机的实战复盘5.1 从82到373从手动跳指针到用堆自动跳指针刷完这三道题之后我突然意识到它们简直是同一个问题的一体三面。82题里while循环弹出的是“所有值等于val的重复节点”这就是在跳过一个不可能是答案的区间378和373里每次从堆里取最小的节点再推进它的后继也是在跳过当前序列中不可能是第K小的部分。差别只是82题用的是手动指针移动378和373用的是堆来自动选择下一个最小候选。用一句话概括这类题的共同骨架是维护一组候选者每次取出最小的候选者更新它的后继重复K次。82题因为只有一条链表所以不需要堆直接用指针即可378和373因为有多个序列并行就要靠优先队列来维护“多个链表当前头节点”的最小值。这个思维模型能迁移到很多看似不相关的题上合并K个有序链表、丑数、超级丑数、有序矩阵找第K小、查找和最小的K对数字底子全是同一个东西。练熟了你看到“第K小”“前K个”“和最小”这些关键词第一反应不再是背各种花哨算法而是先想能不能拆成几个有序序列能不能归并5.2 最容易翻车的几个点这些坑我都是实际踩过的这里集中列出来。82题把“全删”写成“留一个”这是最典型的问题。题目是删除所有重复数字只留不重复的不是每个重复数字留一个。建议写之前先在草稿上画一遍1-2-2-3想清楚最后要的是什么。82题while循环里忘记移动/删除条件有人写着写着会把内层循环写成while(cur-next-val val cur-next)条件顺序反了节点为空时先解引用直接崩。正确写法是先判cur-next非空再取val。378题堆节点不存行列弹出后不知道后继是谁堆里如果只存val弹出后面临“找不到它来自哪一行”的尴尬。存valrowcol是标准做法。373题把两个模型混用如果采用“同时向右和向下扩展”的写法必须加visited去重如果采用“固定nums1为链头单方向推进”的写法不需要visited但不能再往同一个头里乱推。两种模型都对但别掺着写否则要么重复入堆要么漏解。二分统计时用错upper_bound和lower_bound378值域二分要统计“小于等于mid”的个数必须用upper_bound。lower_bound找到的是第一个大于等于mid的位置会把等于mid的值排除数量总是偏小最终答案会错。优先队列比较器方向搞反priority_queue默认是大根堆传greater 之后才会变成小根堆。很多人拿默认的大根堆去跑弹出的永远是最大值答案完全不对。建议写完代码先看一遍弹出的元素是不是最小的。5.3 我的提交前自检清单这三类题我做完了会固定过一遍清单也分享给你空输入是否处理链表为空、矩阵为0、数组为空。头节点是否可能变化链表题一律考虑dummy。重复值是否处理82题重复段一次性跳过二分统计是否含等于mid的数。越界判断是否到位378列越界、373的j1越界。k和输入规模的关系k接近n²用二分k很小用堆。比较器方向确认堆顶是最小元素。二分mid防溢出用left (right - left) / 2。这三题刷完我最大的收获其实不是记住了dummy和排序链表的删除模板而是意识到很多所谓不同题型的题底层都是同一台“有序归并机器”。你在刷题时如果能抽象出“下一个最小元素”这个动作再看到378和373就完全不会慌了。这个模型不止适用于LeetCode很多业务里的Top K查询、多路日志合并、多表排序归并本质也是同一套逻辑。