算是个小小的仪式感吧每年开工我都要把 LeetCode 热题拿出来重新刷一遍今年已经坚持到第三天了。前两天还在做数组和双指针今天轮到链表选了 LC 203、707、206 三道经典的不能再经典的题目。为什么专门挑这三道因为它们正好把链表这个数据结构最核心的三个侧面都覆盖到了——增删改查的常规操作、边界条件的处理、指针交换的底层思维。不管你是刚接触算法的新手还是准备面试想快速找回手感的老手把这三道题吃透链表这块就算真正入门了。我用的语言是 C因为链表这类题对指针操作的表达最直观但文中的思路完全通用用 Python、Java 写也是一样的逻辑。今天这篇不是单纯粘贴题解我会把每一步的踩坑、推导过程、以及做完之后总结出来的通用套路都写清楚尽量做到你跟着走一遍就能真正掌握而不是背题。1. 内容整体设计与思路拆解1.1 为什么 Day3 要集中做链表题链表是一种物理存储单元上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。和数组相比链表的插入和删除不需要移动大量元素时间复杂度是 O(1)前提是已经拿到目标节点的前驱但随机访问就得从头遍历是 O(n)。这个特性决定了链表的题目套路和数组完全不一样数组题大多围绕“双指针原地挪动”链表题则围绕“指针怎么改、边界怎么处理”。我选这三道题还有一个原因它们正好是 LeetCode 上链表分类里最基础的三道入门题难度都是简单或中等却涵盖了链表题 80% 的常见细节203 是节点删除707 是完整的链表类设计206 是指针反转。做完这三道你对链表题的“手感”基本就回来了。1.2 链表题的通用思维方式链表的题表面看起来是代码问题实际上考的是“画图能力”。我在刷链表题时有个习惯先在草稿纸上把节点和指针画出来用箭头表示 next然后模拟每一步操作再落笔写代码。这个习惯帮我省下了大量 debug 时间。链表题最容易出错的点有三个一是操作顺序比如反转链表时如果先把 cur-next 改了后面的节点就找不到了二是边界条件比如链表为空、只有一个节点、操作头节点三是空指针解引用很多报错都是访问了空节点的成员。这三道题练下来这些坑基本都能踩一遍所以特别适合用来做链表专项复健。提示链表题不是靠背题解的而是靠“脑子里有画面”。每道题拿到手先想想指针是怎么走的再动手写。2. LC 203 移除链表元素删除操作的原理与边界细节2.1 题目解读与思路推演题目要求移除链表中所有值等于目标值 val 的节点。比如链表是 1-2-6-3-4-5-6val6处理后应该是 1-2-3-4-5。这道题的暴力思路非常直接从头遍历遇到值相等的节点就把它删掉。但这里有一个核心问题——删除一个节点需要知道它的前驱节点。头节点没有前驱怎么处理最经典的做法有两种一种是单独处理头节点另一种是构造一个虚拟头节点dummy node让头节点也拥有一个“前驱”。我强烈推荐第二种方案。原因很简单它能让你把所有节点都当成中间节点来处理判断逻辑统一了代码自然会简洁很多也少了很多绕来绕去的边界分支。2.2 C 实现与逐步注释class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* dummy new ListNode(0, head); // 虚拟头节点指向真正的头 ListNode* cur dummy; // 从虚拟头开始遍历 while (cur-next ! nullptr) { if (cur-next-val val) { // 删除 cur-next注意不需要移动 cur ListNode* tmp cur-next; cur-next cur-next-next; delete tmp; // 释放内存C 习惯 } else { // 值不相等cur 往后移动 cur cur-next; } } return dummy-next; } };几个细节值得注意。当 cur-next 被删除时cur 本身不能动因为删除后的新 cur-next 还没被检查过如果此时移动 cur 就会漏掉连续相同值的情况。只有 cur-next 的值不等于目标值cur 才能安全地往后挪。这个细节在面试时经常被考也是我自己第一次写时忽略掉的。2.3 复杂度分析与经验提炼时间复杂度 O(n)因为只需要遍历一次链表空间复杂度 O(1)只使用了一个额外指针。这道题做完以后我把它的核心思路提炼成了一条链表操作的通用原则删除节点时操作对象是前驱节点的指针。你会发现 707、206 以及许多更复杂的链表题本质上都是在贯彻这条原则。理解了这一点链表题就成功了一半。3. LC 707 设计链表从零手写一个可用的链表类3.1 题目要求与设计难点LC 707 要求实现一个链表的类支持以下五种操作get(index) 获取指定索引的值addAtHead(val) 在头部插入节点addAtTail(val) 在尾部插入节点addAtIndex(index, val) 在指定索引处插入节点deleteAtIndex(index) 删除指定索引的节点。这题看着简单实际写起来很考验代码的组织能力。五个方法之间互相调用如果不提前设计好公共方法代码会越写越乱。我用的方案是维护一个私有成员 size 记录节点总数维护一个虚拟头节点 dummy 指向真正的头节点这样所有插入和删除操作都统一了逻辑。3.2 核心实现与关键代码class MyLinkedList { private: struct Node { int val; Node* next; Node(int x) : val(x), next(nullptr) {} }; Node* dummy; int size; // 返回索引为 index 的节点的前驱节点方便插入和删除 Node* getPreNode(int index) { Node* cur dummy; for (int i 0; i index; i) { cur cur-next; } return cur; } public: MyLinkedList() { dummy new Node(0); size 0; } int get(int index) { if (index 0 || index size) return -1; Node* pre getPreNode(index); return pre-next-val; } void addAtHead(int val) { addAtIndex(0, val); } void addAtTail(int val) { addAtIndex(size, val); } void addAtIndex(int index, int val) { if (index size) return; if (index 0) index 0; Node* pre getPreNode(index); Node* newNode new Node(val); newNode-next pre-next; pre-next newNode; size; } void deleteAtIndex(int index) { if (index 0 || index size) return; Node* pre getPreNode(index); Node* tmp pre-next; pre-next pre-next-next; delete tmp; size--; } };这段代码里最关键的设计是 getPreNode 函数。无论插入还是删除都需要先找到目标位置的前驱节点把它抽出来做一个公共方法五个接口就都不用重复写遍历逻辑了。这也是实际项目里常见的做法——把重复逻辑下沉为公共函数上层只关注业务语义。3.3 边界情况的处理策略写这题时最容易翻车的是各种边界索引。我总结了三个必查的边界index 为 0也就是操作头节点此时前驱就是 dummy 本身index 等于 size此时是在尾部插入getPreNode(size) 可以正常执行插入时 index 大于 size 要拒绝但 index 等于 size 是合法的删除时 index 等于 size 是非法的。建议各位在本地调试时专门针对这些边界写几组测试用例跑一遍。刷题不能只追求“能过”把边界理清了才算真正掌握。4. LC 206 反转链表指针操作的经典必修课4.1 题目分析与双指针思路反转链表要求把 1-2-3-4-5 变成 5-4-3-2-1。这道题是面试高频中的高频也是检验链表指针思维最经典的题目。第一次接触这题时我最直观的想法是新建一条链表遍历原链表头插法但题目要求原地反转。原地反转的核心在于遍历过程中每一步要当前节点的 next 指向前一个节点。可是如果直接把 cur-next 改成 prev后面那个节点就找不到了所以在修改之前必须先把下一个节点保存下来。这就有了双指针的标准解法。4.2 双指针版本与递归版本对比// 双指针版本 class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* next cur-next; // 先保存后继 cur-next prev; // 指向前驱 prev cur; // 前驱后移 cur next; // 当前节点后移 } return prev; // 最后 prev 就是新头节点 } };双指针版本的代码只有几行但每一步的顺序都很关键。我在草稿纸上给 1-2-3 画了三步操作确认逻辑没有遗漏才动笔。递归版本是另一个思路先递归反转后面的子链表再把当前节点的下一个节点的 next 指向自己。核心代码就两行ListNode* reverseList(ListNode* head) { if (!head || !head-next) return head; ListNode* newHead reverseList(head-next); head-next-next head; head-next nullptr; return newHead; }递归的好处是代码极其简洁但理解成本稍高适合在面试时作为“思路加分项”展示。实际工程中为了避免栈溢出一般还是用迭代也就是双指针版本。两种写法最好都掌握。4.3 从反转链表延伸出的进阶问题做完 206还可以顺手想一想几个变种题反转链表的前 N 个节点反转链表的某个区间LC 92每 K 个一组反转链表LC 25。它们的核心逻辑都是从 206 扩展来的只是边界条件更多、指针操作更繁琐。我在复健计划里把它们放到了后面几天但非常建议你在理解透彻 206 之后再挑战。5. 链表题常见问题与排查技巧实录5.1 高频报错与解决方案速查表刷题过程中难免遇到各种报错我把高频问题和排查思路整理成了表格方便以后快速查阅。典型现象根本原因解决方案运行时提示访问空指针访问了空节点的 next 或 val遍历循环条件写成 cur ! nullptr需要访问 cur-next 时条件写成 cur-next ! nullptr反转链表后输出为空返回了新链表的尾节点返回循环结束后的 prev而不是 head链表出现循环导致超时某处 next 指向了之前的节点画图检查每个节点的 next 指向特别注意最后的节点要指向 nullptr删除节点后 size 没减数据结构维护的 size 与实际不一致增删操作和 size 修改必须成对出现插入位置 index 判断错误混淆合法与非法索引范围记住插入的合法范围是 0 到 size删除是 0 到 size-15.2 我实际踩过的三个坑第一个坑是 206 的递归版本里忘了把 head-next 置空。逻辑上反转到最后原本的头节点应该变成新链表的尾节点如果不置空就会留下一个环。这类问题在 LeetCode 上不一定报错但会直接超时或者导致内存问题非常难排查。第二个坑出现在 707 的 addAtHead 实现上。我一开始直接在里面写了完整的头插逻辑后来发现它和 addAtIndex(0, val) 完全重复导致需要两处维护 size。重构时改成互相调用之后代码量减了不少也少了一个可能漏改 size 的入口。第三个坑是 203 里删除节点时提前移动了 cur。我第一次写的时候判断完相等就 cur cur-next结果链表中连续的相同值会漏删一个测试用例直接没通过。从那以后我形成了习惯删除当前节点的后驱时遍历指针不前进只有当前节点保留时才前进。5.3 调试链表题的实用技巧链表题的调试最怕“凭空想象”。我在本地练习时常用两个技巧第一写一个辅助的 printList 函数把整条链表的每个节点值打印出来每次操作完立刻看输出第二在关键操作前后手动输出 prev、cur、next 的地址或值确认每一步的指针变化是否符合预期。刷题时先用极端用例验证再提交也非常重要。常见极端用例空链表、只有一个节点的链表、删除头节点、反转只有两个节点的链表、目标值在链表首尾连续出现等。这些用例能覆盖大部分边界问题跑一遍再提交通过率会高很多。6. 链表复健后的核心总结与面试应对心得三道题做完我对链表题的信心恢复了不少。复盘了一下发现所有的链表操作其实都可以归纳成三个核心能力找前驱节点、改指针顺序、维护边界条件。找前驱节点对应 203 和 707——删除和插入一定要拿到 target 的前驱改指针顺序对应 206——先保存后继再改 next这个顺序打死都不能变维护边界条件贯穿所有题目——链表为空怎么办、只有一个节点怎么办、操作头节点怎么办这些情况一定要在写代码前就想到。面试时如果遇到链表题我建议按这样的顺序来先用一两分钟说思路条件允许的话画图示意然后告诉面试官“我打算借助一个虚拟头节点来统一处理边界”这句话在很多链表题里都是加分项最后再开始写代码。写的过程中记得边写边说出你在做什么以及为什么这样做这能让面试官 validate 你的思考过程即使代码有小 bug也能体现你的思路是清晰的。下午我又顺手把 203 的删除逻辑换成了递归写了一遍707 用 Python 重写了一遍206 也尝试了区间反转的变体。换语言重新实现一遍对理解数据结构的本质帮助很大建议你们也试试。明天计划进入哈希表专题到时再继续分享。