企业官网建设流程全解析

代码随想录刷到第3天，很多人第一次开始怀疑自己的脑子。前两天数组专题好歹是"下标找位置、连续内存直接算"，思路再绕也有个确定的索引兜底；可一到Day3的链表专题，画风剧变——移除链表元素、设计链表、反转链表，三道题没有一道能靠死记模板混过去，全部在逼你直面指针（引用）到底是怎么在节点之间跳转的。这篇文章把Day3的完整学习路线、每道题的解题思路、完整代码、以及我刷完之后复盘出来的各种坑一次性讲清楚，适合正在准备校招社招、或者链表概念刚入门还没动手写过题的同学。看完之后，你至少能少踩我当年踩过的八成坑。

1. 先看清Day3的版图：三道题分别想训练你什么

1.1 三道题的学习目标

Day3在整条刷题路线里的定位很明确：从数组这种"连续内存的线性结构"，切到链表这种"离散内存的线性结构"。三道题各司其职，缺一不可。

三道题层层递进：203先让你学会"怎么删"；707逼你把"增、删、查"全部实现一遍，边界条件多到怀疑人生；206则更进一步，要你改变链表的连接方向。全部啃完，链表的基本操作才算真正入了门。

1.2 为什么链表值得单独占一天

很多初学者不理解：链表不就是"节点指向下一个节点"吗？有什么好花一整天的？

问题恰恰出在"不就是"这三个字上。链表的逻辑结构极其简单，但物理实现——也就是内存里指针怎么转、什么时候该保存临时节点、什么时候该先移动指针再改指向——非常反直觉。数组里你写arr[i] = arr[i+1]完全不用考虑元素之间的"链接关系"；链表里一行cur.next = cur.next.next就能让一个节点从链表上消失，如果你没有理解这行代码背后发生了什么，出bug时连排查方向都找不到。

Day3就是专门用来"打破数组思维"的。刷完这一天，你会习惯性地思考：操作链表时，我需不需要一个虚拟头节点？我需不需要一个临时指针先把下一个节点存住？这种思维习惯，后面刷二叉树、LRU缓存、跳表等等都会反复用到。

2. 链表理论基础：数组像连排宿舍，链表像散装的集装箱

2.1 存储结构决定了操作方式的差异

数组的内存是连续的。就像一栋连排宿舍，204房间和205房间一定挨着，所以只要知道204在哪，一算偏移量就能直接找到205，这是随机访问O(1)的物理基础。

链表的内存是离散的。每个节点像港口散装堆放的集装箱，集装箱A和集装箱B在物理上可能隔了十万八千里，它们之间的逻辑顺序完全靠每个箱子上贴的那张"下一个箱子在哪"的标签来维持。这张标签，就是单链表每个节点里的next指针。

正因为物理上不连续，链表没法用下标直接跳到第k个节点，只能从头部开始一个节点一个节点地走，所以访问是O(n)；但也正因为每个节点都"各自为政"，只要知道前驱节点，删除和插入只需要改动相邻节点的指针，在已知前驱的情况下，插入删除是O(1)。数组则相反，插入删除往往需要挪动大量元素。

这一反一正，就是后面所有链表题目的底层逻辑来源。

2.2 节点的定义与三种链表形态

在代码层面，链表的基础单位是节点。单链表节点在Java里的典型定义是这样：

public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } }

一个节点只干一件事：存一个值，再记一个"下一位朋友在哪"的地址。就这么简单。

链表还有三种常见形态，刷题必须分清：

• 单链表：每个节点只有next指针，只能单向遍历。无法回头，是三道Day3题目的默认形态。
• 双链表：每个节点有prev和next两个指针，可以双向走。实际工程里更常用，但刷题复杂度更高。
• 循环链表：尾节点的next不指向null，而是指回头节点或某个节点，形成环。约瑟夫问题、环形链表检测之类题目会用到。

把单链表玩熟，是后面一切链表变种的基础。Day3的三道题全都限定在单链表，恰好让我们聚焦最核心的指针操作。

2.3 虚拟头节点：一个改变"头节点命运"的发明

链表题目里最烦人的角色，就是头节点。因为头节点没有前驱。删除一个普通节点，只要让前驱的next绕过它就行；删除头节点呢？没有前驱可以操作，只能单独写一段逻辑处理。

于是就有了虚拟头节点（dummy node）这个极其常用的技巧：在真实头节点前面再加一个不参与业务逻辑的哨兵节点。这个哨兵让原本没有前驱的真实头节点也"变得有前驱了"，所有节点的删除、插入逻辑就统一了——不用再写特判。

这个思想Day3会出现三次，尤其是203题，几乎就是专门为它准备的。

3. 移除链表元素：一个虚拟头节点解决"头节点歧视"

3.1 题面与直接实现

题目很直白：给定链表头节点和一个目标值val，删除链表中所有节点值等于val的节点，返回新的头节点。比如链表1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6，删除所有6之后，应该返回1 -> 2 -> 3 -> 4 -> 5。

思路比题面还直白：遍历链表，发现某个节点的值等于val，就让它的前驱节点绕过它。难点只在一个位置——头节点本身就是目标值怎么办。

不用虚拟头节点的写法，只能把头节点单独拿出来特殊处理：

class Solution { public ListNode removeElements(ListNode head, int val) { // 先处理头节点连续等于val的情况 while (head != null && head.val == val) { head = head.next; } // 此时head要么是null，要么val不等于目标值 ListNode cur = head; while (cur != null && cur.next != null) { if (cur.next.val == val) { cur.next = cur.next.next; } else { cur = cur.next; } } return head; } }

注意第一个while循环为什么用while而不是if：因为可能出现1 -> 1 -> 1 -> 2这种连续多个头节点都要删的情况，一个if根本不够；循环结束条件还要判head != null，防止整条链表全被删光的情况。这两种边界，第一次写的人十有八九会漏掉一个。

3.2 虚拟头节点写法：所有节点一视同仁

上面那种写法没有任何逻辑错误，但代码里混着"头节点特判"和"普通节点删除"两套逻辑，读起来不够统一、也容易漏边界。更推荐的思路是引入虚拟头节点：

class Solution { public ListNode removeElements(ListNode head, int val) { ListNode dummy = new ListNode(-1, head); ListNode cur = dummy; while (cur.next != null) { if (cur.next.val == val) { cur.next = cur.next.next; } else { cur = cur.next; } } return dummy.next; } }

核心差异只有两句：ListNode dummy = new ListNode(-1, head);把原来的head变成"第二号节点"，于是所有节点都成了有前驱的普通节点；最后return dummy.next，因为此时真正的头节点可能已经被删掉了，只有通过dummy才能找到新的头。

这里有个特别容易犯的错误：有人最后会写return head。一旦原头节点的值等于val，head早就被绕过甚至删除了，返回它就是返回了一个"不在新链表上"的节点，测试用例直接错给你看。

我个人的习惯是：只要链表题可能出现头节点变动，无脑先加一个dummy节点。这不叫过度设计，这叫把边界问题消灭在源头。

3.3 复杂度与内存释放提醒

删除链表元素，最坏情况要把整条链表走一遍，时间复杂度O(n)，没有额外存储，空间复杂度O(1)。

如果你是C++选手，还有一个额外的坑：被跳过的节点，比如值等于val的节点，如果用了new创建，不手动delete就会内存泄漏。所以C++写法里，执行cur.next = cur.next.next前通常要先用一个临时指针把待删除节点存下来，删完指针关系后再delete它。Java和Python因为有垃圾回收机制，不需要手动处理，但也正因此，很多Java程序员初学C++链表题会在这里栽跟头。面试时如果用的是C++，这个细节往往是个加分项。

4. 设计链表：dummy head + size，把五个方法写成一套严丝合缝的逻辑

4.1 题面与整体设计决策

这一题是Day3的重头戏。它不考任何高级算法，单纯要求你实现一个单链表类，包含五个方法：

• get(index)：获取第index个节点的值，无效索引返回-1
• addAtHead(val)：在头部插入
• addAtTail(val)：在尾部插入
• addAtIndex(index, val)：在第index个节点前插入；index等于链表长度时插入到尾部；index大于链表长度则什么都不做；index为负数则插入到头部
• deleteAtIndex(index)：删除第index个节点，无效索引什么都不做

你要是直接上手写，大概率会经历"写完了、一跑、边界用例挂了、改、又挂"的循环。这题的核心难点不是单个方法，而是五个方法共享同一套状态时，状态必须始终保持一致。

我推荐的设计决策就两条，足够扛住全部需求：

1. 使用虚拟头节点。这样addAtIndex和deleteAtIndex里，统一通过"找到第index个节点的前驱"来操作，不需要为头节点特判。
2. 维护一个size变量。插入节点就size++，删除节点就size--。没有size，addAtTail和addAtIndex的合法性判断、以及遍历步数计算，会全部陷入混乱。

注意，这个类里的虚拟头节点不需要存有效值，它只是个"锚点"。而所有方法对"第index个节点"的定义，都要和size保持一致：节点编号从0开始，size等于节点总数，所以最大合法索引是size-1。

4.2 五个方法的逐个实现与边界条件

先看完整实现，再逐段拆解：

class MyLinkedList { private int size; private ListNode dummyHead; public MyLinkedList() { size = 0; dummyHead = new ListNode(0); } public int get(int index) { if (index < 0 || index >= size) { return -1; } ListNode cur = dummyHead.next; for (int i = 0; i < index; i++) { cur = cur.next; } return cur.val; } public void addAtHead(int val) { addAtIndex(0, val); } public void addAtTail(int val) { addAtIndex(size, val); } public void addAtIndex(int index, int val) { if (index > size) { return; } if (index < 0) { index = 0; } size++; ListNode pre = dummyHead; for (int i = 0; i < index; i++) { pre = pre.next; } ListNode newNode = new ListNode(val); newNode.next = pre.next; pre.next = newNode; } public void deleteAtIndex(int index) { if (index < 0 || index >= size) { return; } size--; ListNode pre = dummyHead; for (int i = 0; i < index; i++) { pre = pre.next; } pre.next = pre.next.next; } }

get方法：先校验index < 0 || index >= size。这里最容易漏的是index >= size这个条件，比如size为3，合法索引是0、1、2，index为3就已经越界了。如果忘了这个判断，cur会在循环中走到null，然后对null调用.val，直接空指针异常。遍历步数上注意，get(0)应该一步不走，直接返回dummyHead.next的值，所以循环从i=0; i<index走index步，恰好落在目标节点上。

addAtIndex方法：这是五个方法里最复杂的。规则要求index等于size时插入到尾部、index大于size时什么都不做，所以合法条件是index <= size，超出就直接return。index小于0时题目要求插入到头部，直接归零处理。确定能插入后，先size++，再让pre指针从头节点前驱也就是dummyHead开始走index步。虽然这题用虚拟头节点，但为什么步数取index而不是index+1？因为我们要找的是插入位置的前驱。假设要在第0个节点前插入，前驱就是dummyHead，走0步；要在第2个节点前插入，前驱是第1个节点，走2步。这个"前驱和索引的换算关系"是整道题最容易出偏移错误的地方。

addAtIndex里的插入顺序也有讲究。标准动作是：先让新节点的next指向原本的后继，再把前驱的next指向新节点。也就是代码里newNode.next = pre.next; pre.next = newNode;这两行的顺序不能反。如果先执行pre.next = newNode，那么原本pre.next指向的后继信息就丢失了，新节点会找不到自己的后继。这个"先接右、再接左"的顺序，可以迁移到几乎所有链表插入场景。

deleteAtIndex方法：同样先去判断索引合法性，注意这里判断的是index >= size而不是>size，因为删除时索引等于size已经不存在对应节点了。合法就size--，然后找前驱节点，让它跳过待删除节点：pre.next = pre.next.next。Java不用手动释放节点，垃圾回收会自动处理。

addAtHead和addAtTail：这两个方法最取巧的实现就是直接复用addAtIndex(0, val)和addAtIndex(size, val)。如果自己再单独写一遍遍历逻辑，代码重复不说，还容易在维护size时出现多个入口不一致的问题。凡是能在底层方法上复用的，尽量复用。

4.3 这题的自测清单

这题力扣给的测试用例其实覆盖了大部分边界，但我建议任何人在提交前至少自己额外验证这几个场景：

• 在空链表上调用get(0)，应该返回-1
• 在空链表上addAtHead然后get(0)，应该拿到刚插入的值
• addAtIndex插入到index大于size的位置，链表不该有任何变化
• 删除最后一个节点后，链表size为0，再调用get(0)返回-1
• 连续多次deleteAtIndex(0)清空链表，中途不能有任何索引越界异常

我自己第一次写这题时，忘了在deleteAtIndex里更新size，结果前几个用例全过，一到删除后继续查值的用例就崩。这种state不一致的bug，靠肉眼很难看出来，所以一定要养成"操作完立即更新size"的肌肉记忆。

5. 反转链表：从"改指针"到"记住下一个"，差的只是一个temp

5.1 题面与迭代解法

反转链表有多经典不用多说，题目就一句话：给你单链表的头节点head，反转链表，返回反转后的新头节点。1 -> 2 -> 3 -> 4 -> 5变成5 -> 4 -> 3 -> 2 -> 1。

很多人第一次做这题的思路是：新建一个链表，把原链表的节点一个个头插进去。这确实能过，但不是题目要考的——它考的是原地反转，也就是不额外开链表，只通过修改指针方向完成逆转。空间复杂度要从O(n)压到O(1)。

迭代法的标准姿势是三个指针：pre、cur、temp。

class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; ListNode temp = null; while (cur != null) { temp = cur.next; // 先保存下一个节点，否则指针一改就找不到了 cur.next = pre; // 让当前节点指向前一个节点 pre = cur; // 前驱指针后移 cur = temp; // 当前指针后移 } return pre; } }

用大白话拆解每一步：

• 初始时pre是null，cur是head。因为反转后的链表，原来的头节点要变成尾节点，而尾节点的next必须指向null，所以cur第一次要指回pre，也就是null。
• 进入循环后，第一件事是temp = cur.next。这一步是灵魂所在。只要执行了cur.next = pre，当前节点和它原本下一个节点的连接就断了，如果不先用temp把下一个节点记下来，后面的遍历就彻底断线了。
• 然后pre = cur和cur = temp相当于把两个指针整体向后平移一位，开始处理下一对相邻节点。
• 循环结束条件是cur == null，说明已经走完了原链表的所有节点。此时pre停在原链表的尾节点上，也就是反转后的头节点。

5.2 为什么temp是无数人的第一个坑

我见过太多人在这一步翻车，包括我自己。很多人想到需要反转指针方向，写出的第一版是这样：

while (cur != null) { cur.next = pre; pre = cur; cur = cur.next; // 画风突变，这里cur.next已经指向pre了！ }

看起来逻辑很顺，但cur.next在上一行刚被改成指向pre，再执行cur = cur.next，cur不但没有前进到原先的下一个节点，反而直接跳回了前一个节点。结果就是死循环或者链表断裂。这就是为什么必须在改变cur.next之前，用temp把原始后继保存下来。

这个教训可以抽象成一句话：凡是要修改一个节点的next指针，先问自己一句——原来指向的下一个节点，我还保存着吗？没有保存就先存，这是链表操作里最重要的安全习惯，比任何技巧都管用。

5.3 递归解法：换个角度看同一件事

迭代解法是"从头到尾一个一个掰指针"，递归解法则是"每次只处理两个节点，剩下的交给递归"。

class Solution { public ListNode reverseList(ListNode head) { return reverse(null, head); } private ListNode reverse(ListNode pre, ListNode cur) { if (cur == null) { return pre; } ListNode temp = cur.next; cur.next = pre; return reverse(cur, temp); } }

这个写法其实是迭代法的逐行翻译：pre对应迭代里的pre，cur对应迭代里的cur，每次递归调用就等于迭代循环里指针后移的那两步。终止条件cur == null返回pre，与迭代return pre完全对应。

还有另一种更"递归味"的写法，从链表尾部开始翻转：

public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; }

这种写法理解起来需要一点想象力：先假设head.next之后的子链表已经反转完毕，那么此时head.next恰好是新链表的尾节点，只要让这个尾节点再指向head，就完成了两个节点的连接，最后把head的next置为null，断开它和原后继的关系。递归的写法代码极短，但调用栈的深度等于链表长度，链表很长时理论上没有迭代法那么稳。面试时如果没有明确要求，我通常推荐先写迭代法，不容易出错，也方便讲清楚。

6. Day3实战错题本：五个高频bug与我的排查套路

6.1 高频bug之一：遍历终止条件写错

链表题里while (cur != null)和while (cur.next != null)的区别，是新人最容易混淆的点。前者能遍历到最后一个节点，后者只能停在倒数第二个节点。203题的循环用while (cur.next != null)是刻意的，因为我们每一步都要判断"下一个节点要不要删"，如果cur走到了尾部null，cur.next直接空指针。而206题的while (cur != null)也是刻意的，因为我们要处理每个节点本身。先想清楚循环体里需要cur处于什么状态，再决定终止条件，顺序不能反。

6.2 高频bug之二：707忘记维护size

这是我做设计链表时踩得最惨的一坑。addAtIndex里我写了size++，但deleteAtIndex里忘了size--。结果链表真的删掉了节点，size却仍然虚高，下一次get就会遍历到null节点上。排查方法也很朴素：在每一个方法的入口和出口打印size，对比一下操作前后size是否符合预期。一旦发现"操作成功但size没变"，立刻就能定位。

6.3 高频bug之三：返回了错误的头节点

203题很多人最后写return head，但此时原头节点可能已经被删除，正确的头节点只能通过dummy.next获得。这个问题本质上是没有想清楚"虚拟头节点出现后，真实头节点是动态的"。以后凡是用了dummy节点，最后返回时先条件反射地想到dummy.next，而不是那个可能早已失效的局部变量head。

6.4 一道题卡住时的标准排查流程

链表题卡住时，盯着代码干想是最低效的。我的固定流程是：

1. 画图。把链表画成方框加箭头，标出pre、cur、temp，一步步模拟指针变化。这个过程看着笨，却是定位"指针丢失""环成死循环"最有效的手段。
2. 写一个打印函数。很多链表题都值得花30秒写一个printList辅助函数，每操作几步就打印一次当前链表。不要嫌麻烦，它带来的调试效率提升远超那30秒成本。
3. 造最小测试用例。长度1的链表、长度2的链表、空链表、所有节点值都相同的链表，这四个用例能覆盖链表题八成以上的边界坑。
4. 复现题目给的例子。如果跑不过就逐步走查，看是哪一步的指针关系和预期不符。

6.5 刷完Day3之后的复习建议

按记忆曲线的规律，Day3的内容在刷完的第二天就会开始遗忘。我的建议是：隔48小时后，不看书不查答案，把三道题重新各写一遍，重点检查707的边界判断和206的temp保存逻辑，这一遍能暴露出大量"当时以为会了、其实只是背下来了"的问题。之后再隔一周做第三遍，这一遍你要追求的是不看任何提示一口气写对，同时能在口头清晰地讲出每一步为什么这么做——这才是面试考链表时真正需要的状态。

我个人刷完Day3最深的体会是：链表题的代码量都不大，难的是在动手之前脑子里先有一条清晰的指针移动路线。路线清楚了，写代码就是翻译；路线模糊，写出来的代码就是一堆等待边界用例来打脸的拼凑。Day3的价值，恰恰就是逼你建立这条"先想清楚指针怎么走，再动手写"的思维习惯。这个习惯一旦养成，后面刷树、图、各种链表的变种题，都会顺畅得多。