1. 为什么第三天就要死磕链表链表这东西新手容易觉得简单老手又容易在细节上翻车。刷题进度到第三天正好是数组和字符串玩得差不多、开始接触指针操作的节点。这一天安排的三道题——第203题移除链表元素、第707题设计链表、第206题反转链表——看起来是三个独立题目实际是一条完整的链表基本功训练链。把这三道题吃透后面再遇到环形链表、相交链表、两两交换节点都会轻松很多。先说清楚适合谁看。如果你刚刚学完数组想搞明白“节点”“指针”“哨兵”这些概念到底在说什么或者你在刷题平台上做过几道链表题但总是因为边界条件报错又或者面试前想快速把链表操作捡起来那么这份记录就是按实际踩坑过程写的。我会把每一道题的思考方式、代码写法、容易错的地方都拆开讲尽量让没有系统学过数据结构的人也能一步步跟上。为什么要单独把链表拎出来练因为数组和链表的思维模式完全不一样。数组是连续内存靠下标找数据想删一个元素得把后面所有元素往前搬链表是零散节点靠指针串起来想删一个节点只需要改前后两个节点的指向。这个区别决定了链表题的代码量不大但指针操作一旦画错整个链表就拧成一团。我自己见过不少同学数组题写得很顺一到链表就栽在“空指针访问”“死循环”“丢链表头”这三件事上。这三道题恰好把这些问题全部覆盖了值得慢慢磨。2. 先想通这三道题的关系再动手写代码2.1 从数组到链表思维上要换哪些东西在数组里我们习惯用“下标”描述位置arr[0]、arr[3]逻辑非常直白。链表里没有下标只有“当前节点”和“下一个节点”。这样描述位置的方式从“哪里”变成了“怎么走”。比如要找到第3个节点得从链表头开始沿着next指针走两步。这个转换说难不难说简单也不简单难在写代码时容易把自己绕晕到底当前指针是指向第一个节点还是指向第一个节点的前一个节点不同写法差一个节点的距离结果就是边界全错。还有个更重要的变化数组的元素是“值”链表节点是“对象”。我们在数组里交换两个位置直接换值就行链表里要调整的是每个节点的next指针。很多人第一次写反转链表时脑子里想的还是“把值反过来”结果写完发现链表根本没变。值可以拷贝但指针关系只能重新连接。这就是为什么链表题通常会要求你画图不画图纯靠脑子想很容易在某个节点上迷路。2.2 三道题的递进关系操作现有节点、自建完整结构、重新定义连接如果把这三道题放在同一张训练表上看逻辑非常清楚。第203题是“向外输出结果”给你一条已经存在的链表让你删掉所有符合条件的目标节点。这题的核心在于遍历链表时如何用一个当前指针和一个前驱指针协同工作以及如何处理头节点删除的边界。第707题是“从零造一个链表类”你自己定义节点、维护链表长度、实现头部插入、尾部插入、指定位置插入和删除、按下标取值。这题等于把链表的所有基础操作完整做了一遍做完了你对虚拟头节点、指针步数、边界长度的理解会扎实非常多。第206题是“重排既有连接”不新增节点也不删除节点只是把每个节点的next方向从指向后一个变成指向前一个。它训练的是你在原地修改指针结构时如何保证不丢节点、不回路。换句话说第203题教你“在链表上做判断”第707题教你“把链表的规则定出来”第206题教你“把链表的连接重新拉一遍”。很多同学刷完这三题后最明显的感受是链表不再是一堆飘着的箭头而是一套有迹可循的操作逻辑。这也是这段训练链设计得最妙的地方。3. 第203题移除链表元素先学会怎么“跳过”节点3.1 题意到底在考什么题目要求很简单给定一个链表头节点和一个整数值val删除链表里所有存储的值等于val的节点。简单来说就是把这个链表里等于某个值的节点全部摘掉。最直观的思路是从头开始遍历如果遇到一个节点的值等于val就把前一个节点的next指向这个节点的next。这样当前节点就被“跳过去”了链表没有它也能完整串起来。这个操作对应到生活里就像整理一串手链某个珠子不想要了不是把整串拆了而是把珠子两边相邻的珠子直接连起来。但问题马上就来了如果删除的是第一个节点怎么办第一个节点没有前一个节点。常见做法是单独判断如果head的值等于val就把head指向head-next。这种做法能跑但每次删除头节点都要写一遍相同的逻辑而且很容易漏判——新增一个头节点后又需要处理。这个痛点就引出了链表里非常常用的一个技巧虚拟头节点。3.2 用虚拟头节点把特判变成统一逻辑所谓虚拟头节点就是自己new一个额外的节点让它的next指向原来的链表头然后把这个节点当作遍历的起点。这样原本的“头节点”也有一个统一的前驱节点了所有删除操作都遵循同一套规则判断cur-next的值是不是val如果是就修改cur-next的指向。整个过程不需要再关心“我删的到底是不是原链表的第一个节点”。代码长这样ListNode* removeElements(ListNode* head, int val) { ListNode* dummy new ListNode(0, head); ListNode* cur dummy; while (cur-next ! nullptr) { if (cur-next-val val) { ListNode* tmp cur-next; cur-next cur-next-next; delete tmp; } else { cur cur-next; } } head dummy-next; delete dummy; return head; }我来逐行解释一遍这个写法的思路。dummy就是我们说的虚拟头节点随便给它一个val这里用0反正不会被读到。cur从dummy开始而不是从head开始。进入循环后每次盯着cur-next的值如果它等于val说明要删掉这个节点。删除前先用tmp把要删的节点存下来然后把当前节点的next指向要删节点的下一节点再删除tmp。注意这里删除之后cur不要移动因为cur-next此时已经是新的节点它可能还是val必须继续处理。只有当前节点的下一个节点值不等于val时cur才往前走一步。最后把dummy的next当作新链表头返回。这里有一个很多人第一次写会犯的错在删除节点后还把cur移动到了cur-next。假如链表中连续两个节点值都是val你删除第一个后cur移到了原来第二个节点也就是现在已经变成“新第一个”的位置然后循环判断cur-next是否等于val实际上你把应该删除的第二个节点漏过去了。所以删除后cur原地不动这一步是必须记住的。3.3 什么时候用临时指针什么时候直接改指向不少初学者问我直接就cur-next cur-next-next不也能跳过吗为什么非要先存一个tmp再delete两种写法的区别在于是否释放内存。在支持手动管理内存的语言里如果不删除被摘掉的节点它就会一直占据内存。刷题时判题系统通常不检查内存泄漏结果能过但到了工程上或者在你本地的内存检测工具里问题就暴露了。另外如果你不delete而后面代码里无意中又通过某个旧指针访问那块区域就会读到已经被重新使用的内存产生非常难查的bug。我的习惯是在链表修改类题目里被摘下来的节点统一用tmp保存后delete除非题目明确说不用处理。注意删除节点之前必须先保存它的指针再改变前驱的next。顺序反了这个节点就找不到了既没法delete也等于把一段内存弄丢。还有个小细节最后为什么要delete dummy因为虚拟头节点也是我们自己new出来的不是原链表的一部分函数结束后它没用了不释放就会泄漏。有些刷题平台的判题器不会管这个但养成好习惯很重要。另外如果我把head重新赋值成dummy-next然后再delete dummy顺序不能反。因为dummy-next就是我们需要的链表头如果先delete dummy再取dummy-next就是访问已释放内存行为未定义。4. 第707题设计链表把链表的操作规则彻底揉碎4.1 类结构和设计思路第707题不是给你一条链表去操作而是让你自己实现一个链表类。题目要求这几个功能按索引获取节点值在头部插入在尾部插入在指定索引插入删除指定索引的节点。这道题做完你对链表内部结构的理解会有一个质变。我把它当成“试着自己造一个容器”来写而不是单纯为了过题。先确定内部状态一个链表需要知道自己有多少个节点还需要一个可以统一处理各类插入删除的起点。我选择了两个私有成员size记录链表元素个数dummyHead作为虚拟头节点。选择虚拟头节点的理由和第203题一样让所有插入删除操作都站在“某个节点之后插入/删除”的角度避免单独处理头节点。节点结构可以用一个内部结构体struct ListNode { int val; ListNode* next; ListNode(int v) : val(v), next(nullptr) {} };类的基本骨架class MyLinkedList { private: ListNode* dummyHead; int size; public: MyLinkedList() : size(0) { dummyHead new ListNode(0); } // 其他方法 };为什么不用尾节点说实话加上尾节点可以加速尾部插入但代价是每种操作都要维护尾节点的正确性容易出bug。这道题对时间复杂度的要求并不高先用O(n)的尾部插入把思路写对等熟练后再考虑优化也不迟。我见过加了尾节点反而把自己绕晕的因为没有在删除尾节点时正确更新tail指针。4.2 get方法从第一个有效节点走index步get的返回值是第index个节点的值。注意第0个节点就是链表头节点。代码是这样int get(int index) { if (index 0 || index size) return -1; ListNode* cur dummyHead-next; while (index--) { cur cur-next; } return cur-val; }这里有个细节cur dummyHead-next直接跳到第一个有效节点。因为get要取的是第index个节点而不是它的前驱。如果从dummyHead开始走index步走到的是第index个节点的前驱那取到的值就错位了。很多人在get和其他插入删除方法之间切换时会把起点搞混我的记忆方式是凡是“取节点”的操作从第一个有效节点开始走凡是“在某个位置前插入/删除”的操作需要定位到该位置前一个节点这时候从dummyHead开始走。4.3 addAtHead和addAtTail两种最基础的插入头部插入很简单把新节点接到dummyHead后面。注意顺序void addAtHead(int val) { ListNode* node new ListNode(val); node-next dummyHead-next; dummyHead-next node; size; }先让node指向原第一个节点再让dummyHead指向node。顺序一旦反了先把dummyHead-next改成node那么原来那个节点就找不到了因为node的next还没有指向它。尾部插入需要从头遍历到最后一个节点。最后一个节点的特征是next nullptr。所以void addAtTail(int val) { ListNode* cur dummyHead; while (cur-next ! nullptr) { cur cur-next; } cur-next new ListNode(val); size; }这里cur从dummyHead开始。即使链表为空dummyHead-next是nullptr循环直接不执行cur就是dummyHead然后给dummyHead-next赋上新节点。完美兼容空链表的情况。4.4 addAtIndex和deleteAtIndex边界条件最密集的地方指定位置插入的规则是如果index等于链表长度插在尾部如果index大于链表长度不操作如果index小于0按头部插入处理。这是题目的原意。我写成直接return非法值或直接忽略。void addAtIndex(int index, int val) { if (index 0 || index size) return; ListNode* cur dummyHead; while (index--) { cur cur-next; } ListNode* node new ListNode(val); node-next cur-next; cur-next node; size; }这里的while (index--)是从dummyHead开始走index步。比如index等于0循环不执行cur就是dummyHead插入位置正好是链表最前面index等于size循环走size步cur停在最后一个节点插入位置是链表尾部。这个设计相当优雅也相当容易写错。如果你写的是while (index)或者while (index 0) { index--; }效果不一样必须自己推一遍。删除方法更考验边界void deleteAtIndex(int index) { if (index 0 || index size) return; ListNode* cur dummyHead; while (index--) { cur cur-next; } ListNode* tmp cur-next; cur-next cur-next-next; delete tmp; size--; }区别在于index size的情况插入可以允许在size的位置因为插在末尾是合法的删除如果index size那已经越界了所以条件是index size返回。这里犯的错通常是把插入的和删除的搞混结果在链表为空时莫名访问空指针。急性子注意设计链表类时每个修改操作必须像软件工程里的事务一样同步维护size。增了不增size、删了不删size后面get和deleteAtIndex的判断全部错乱。这种问题排查起来非常恼火。4.5 设计链表最容易踩的坑我一次说全第一个坑没有维护size。很多实现从头到尾遍历判断边界导致get越界时返回错误值或者插入时明明是第size个位置却走了nullptr。第二个坑忘记释放内存。new出来的节点如果只断开引用不delete长跑程序内存会持续增长。虽然刷题无感但写本地项目时会被静态检查工具标红。第三个坑get和addAtIndex的初始位置搞混。get从dummyHead-next出发addAtIndex从dummyHead出发。为什么因为get要找的是目标节点本身而插入要找的是目标节点的前驱二者天然差一位。第四个坑删除后不把tmp置空或重复delete。delete之后指针变野指针后续再delete会崩溃。好的习惯是delete后顺手置为nullptr。第五个坑没有处理链表为空时deleteAtIndex(0)。如果size为0边界判断index size会直接拦住所以代码是安全的。但我见过有人把边界条件写成index size就把空链表直接干翻了。5. 第206题反转链表把每个节点的next拧个方向5.1 迭代法用两个指针轮流往前走反转链表是链表题里最经典的题目没有之一。题目要求把一条链表完全倒过来比如1-2-3-4变成4-3-2-1。第一眼看上去很吓人因为我要改变每一个节点的next方向又不能丢掉还没遍历到的节点。迭代法的核心思路是准备两个指针prev指向已反转部分的前一个节点cur指向当前要处理的节点。最开始prev是nullptrcur是head。每一步先把cur后面的节点用next保存起来再把cur的next指向prev也就是把当前这个箭头反拧过来随后prev和cur各自向前移动一步。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; }为什么要先保存next因为一旦执行cur-next prevcur原来的下一个节点就找不到了。链表是单向的没有保存就会直接断链后面全部丢失。这三行顺序是固定的保存next、改指向、移动prev和cur。绝不能改成先移动cur再改指向那样prev和cur的关系就乱套了。循环结束后cur变成nullptr此时prev恰好指向原链表最后一个节点也就是反转后新的头节点所以返回值是prev。一个很常见的思想实验是只用一个指针循环能不能反转不能因为单链表节点的next被修改后你无法回到原来的后继。一定要有两个指针加上一个临时保存总共三个变量轮转。5.2 递归法先假设后面已经处理好递归版的理解方式和迭代版完全不同但代码更短。核心思想是反转一个链表可以看成把第一个节点接到“反转后的剩余部分”末尾。递归的终止条件是链表为空或者只有一个节点那么它已经反转好了直接返回。ListNode* reverseList(ListNode* head) { if (head nullptr || head-next nullptr) { return head; } ListNode* newHead reverseList(head-next); head-next-next head; head-next nullptr; return newHead; }我详细讲这个递归过程因为很多朋友在这里卡住。假设链表是1-2-3。调用reverseList(1)由于1-next不是空进入递归调用reverseList(2)。同理进入reverseList(3)。在reverseList(3)里3-next是nullptr返回3。回到reverseList(2)这一层newHead是3。此时执行head-next-next headhead是2head-next是3所以让3的next指向2然后让2的next指向nullptr返回newHead3。回到最外层head是1head-next-next就是2-next指向1再把1-next指向nullptr。整个链表变成了3-2-1。这个过程中最关键的是理解递归函数返回的是“反转后的新头”而不是“当前层原来的头”。很多初学者拿到递归头节点以为返回head即可结果链表乱掉。实际上最外层递归拿到的新头是原来的尾节点只有它才是反转后的头节点。5.3 反转链表易错点清单容易错的地方主要集中在两点一是忘记处理递归中的环二是迭代中移动指针顺序有问题。在迭代里cur-next prev执行后如果不把cur移动到next而是直接把prev赋成cur就会死循环。我见过的典型错误是这样while (cur ! nullptr) { ListNode* next cur-next; prev cur; cur-next prev; // 这样写完全错了cur-next被指回自己 ... }这种顺序错位会导致节点指向自己在打印时表现为无限循环。所以在测试反转题时我习惯在循环里加一个计数器或打印防止死循环把终端刷爆。在递归里容易漏的是head-next nullptr。如果不把这句写上原来的头节点还指向第二个节点会构成一个环。特别是原链表只有两个节点时1-2会被反转成2-1但如果最后不把1-next断开1又指向2形成了1-2的环。我之前调试这个bug花了差不多半小时最后用打印函数发现最后一个节点打印完之后又跳回前面的节点。6. 链表调试三板斧打印函数、边界用例、内存习惯6.1 写一个通用的打印函数链表的调试没法像数组那样直接打印全部所以我的习惯是刷题前先备一个打印函数。它不需要多复杂能把整条链表从头到尾输出成“1-2-3”这样的形式就够了。代码非常简单void printList(ListNode* head) { ListNode* cur head; while (cur ! nullptr) { std::cout cur-val; if (cur-next ! nullptr) std::cout -; cur cur-next; } std::cout std::endl; }用这个函数配合测试用例可以在关键步骤后输出链表状态。比如反转链表的方法里每次处理完一个节点后打印一遍指针变化就看得清清楚楚。如果没有这个函数遇到死循环只能盲猜效率低很多。6.2 三道题通用的边界用例集合链表题的边界情况其实非常固定练多了能形成条件反射。我整理了一份使用频率特别高的用例清单场景测试用例作用空链表removeElements(null, val)确保方法不崩溃单节点1删除值1或删除其他值检查头节点更新删除头节点1-2删除1检查虚拟头节点是否生效删除尾节点1-2删除2检查cur-next为空时处理连续重复值1-2-2-3删除2检查删除后cur是否停留原地addAtIndex边界在index0和indexsize插入检查前驱定位deleteAtIndex越界index为负数或等于size检查合法性判断反转的环用两个节点反转检查旧头next是否断开检查递归结尾置空每次写完链表题把这份清单过一遍基本能消灭80%的隐藏bug。我在本地刷题时经常会为这些用例写几行简单的断言函数比如判断反转后第一个元素是不是原链表的最后一个元素一旦输出不符合预期就能快速定位。6.3 关于内存释放我最后唠叨两句很多刷题平台用的是C的判题环境但并不会对每个用例做内存泄漏检测所以即使你new了一堆节点不delete提交也能通过。我见过有人因此完全不写delete次数多了就养成了坏习惯。等你到了需要写长生命周期服务的项目里这种习惯会让内存占用一路飙升。最好的做法是从刷题第一天就严格要求每条链上你new出来的节点要么由链表类在析构函数里统一清理要么在删除操作中立即delete。比如设计链表这类题最好补一个析构函数~MyLinkedList() { ListNode* cur dummyHead; while (cur ! nullptr) { ListNode* next cur-next; delete cur; cur next; } }千万别小看这个析构函数它能帮你验证自己的代码没有产生环或者悬垂指针。如果链表里出现了环释放操作会死循环在本地一跑就暴露了。这也是一个非常有效的检查方法。7. 我刷完这三题之后最想说的体会其实最开始刷链表我也觉得虚拟头节点是个没必要的东西宁可多写几个if分支。后来被第203题的连续重复节点搞崩过一次才老老实实用虚拟头。第707题让我彻底理解了为什么所有标准库的容器都要花费那么多精力去维护“结构不变式”——那个size变量就是一个例子。第206题则是对递归的一次很好的脱敏训练想明白之后很多树的递归题目也变得顺了。如果你今天刚开始练这三道题我的建议是别急着追求一次bug-free先把每个方法的执行过程在纸上画一遍特别是第707题那种多方法类画一次胜过读十遍代码。画的时候重点标出每次操作后链表的头在哪里、size是多少。等画明白了再回到编辑器里写代码你会发现手速突然快了很多。这三道题不一定非要在同一天刷完但最好连续刷。因为它们之间是一环扣一环的虚拟头节点在203里用了一次在707里又用了一次双指针思想在203里初见端倪在206里成为核心对边界条件的敏感度则从203一直贯穿到707。真正把这一套打下来你再看各种链表面试题脑子里会自动浮现出每一步指针的移动图景——那个状态才是刷链表题应该有的感觉。