企业官网建设流程全解析

如果你在搜索引擎里搜“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->5，83题返回1->2->3->4->5，82题返回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 四个容易翻车的边界

我实际提交时，第一次就挂在边界上。这里给你列全：

1. 空链表和单节点链表：直接返回head，后面的while循环会空指针报错，所以开头必须判掉。

2. 头节点开始连续重复：比如1->1->1->2->3。如果没有dummy节点，返回逻辑会非常别扭。dummy节点在这里的价值就体现出来了：头节点也可以像普通节点一样被“跳过”，最后返回dummy.next就是新头。

3. 尾部重复：比如1->2->3->3->3。内层while循环里必须写cur->next非空判断，否则当cur->next移到nullptr时，取cur->next->val会崩。

4. 全部重复：比如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(vector<vector<int>>& matrix, int k) { int n = matrix.size(); priority_queue<Node, vector<Node>, greater<Node>> 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(vector<vector<int>>& 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(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: vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) { vector<vector<int>> res; int m = nums1.size(); int n = nums2.size(); if (m == 0 || n == 0 || k <= 0) return res; auto cmp = [&](const pair<int, int>& a, const pair<int, int>& b) { return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second]; }; priority_queue<pair<int, int>, vector<pair<int, 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，真正的和是每次比较时当场算出来的。这样做的好处是节省空间，不需要把和值单独存一份。

还有个关键设计：每条链表只往j+1方向推进。这意味着同一个数对只会从一个链头进入堆，不会重复入堆，所以不需要像某些写法那样维护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，弹出后面临“找不到它来自哪一行”的尴尬。存val+row+col是标准做法。

373题把两个模型混用：如果采用“同时向右和向下扩展”的写法，必须加visited去重；如果采用“固定nums1为链头，单方向推进”的写法，不需要visited，但不能再往同一个头里乱推。两种模型都对，但别掺着写，否则要么重复入堆，要么漏解。

二分统计时用错upper_bound和lower_bound：378值域二分要统计“小于等于mid”的个数，必须用upper_bound。lower_bound找到的是第一个大于等于mid的位置，会把等于mid的值排除，数量总是偏小，最终答案会错。

优先队列比较器方向搞反：priority_queue默认是大根堆，传greater 之后才会变成小根堆。很多人拿默认的大根堆去跑，弹出的永远是最大值，答案完全不对。建议写完代码先看一遍弹出的元素是不是最小的。

5.3 我的提交前自检清单

这三类题我做完了会固定过一遍清单，也分享给你：

• 空输入是否处理：链表为空、矩阵为0、数组为空。
• 头节点是否可能变化：链表题一律考虑dummy。
• 重复值是否处理：82题重复段一次性跳过，二分统计是否含等于mid的数。
• 越界判断是否到位：378列越界、373的j+1越界。
• k和输入规模的关系：k接近n²用二分，k很小用堆。
• 比较器方向：确认堆顶是最小元素。
• 二分mid防溢出：用left + (right - left) / 2。

这三题刷完，我最大的收获其实不是记住了dummy和排序链表的删除模板，而是意识到：很多所谓不同题型的题，底层都是同一台“有序归并机器”。你在刷题时如果能抽象出“下一个最小元素”这个动作，再看到378和373就完全不会慌了。这个模型不止适用于LeetCode，很多业务里的Top K查询、多路日志合并、多表排序归并，本质也是同一套逻辑。