最近帮人排查一个链表的 bug代码结构本身不难绕了一整晚才发现问题出在头插法上。类似的场景我带过不少同学有人把 Node 的 next 指针绕晕有人插完 1-2 结果输出 2-1还有人一跑空链表就空指针。Java 单链表插入基本操作就三种头插法、尾插法、任意位置插入法。这三样看着是最基础的东西但几乎所有链表题反转、回文、合并、排序翻来覆去用的都是这三个插入操作里的那几行指针改动。这篇我就把 Node 设计、三种写法的代码和执行顺序、边界条件、复杂度账一次讲透顺便把我去年代码里真实踩过的坑也放进来。目标读者很明确刚学完 Java 集合框架准备刷链表题但总是被指针绕晕的人面试前要快速过一遍基础数据结构的人以及想搞清楚链表性能为什么是 O(1) 插入、O(n) 查找的人。看完这一篇你自己就能手工写出“设计链表”这类题目。1. 先把问题讲透插入操作到底难在哪1.1 数组移动和链表改指针是两套完全不同的世界观数组插入核心是“挪”。ArrayList 的 add(index)底层是 System.arraycopy 把 index 之后的元素整体右移一位然后把新元素放进去。这个过程需要移动物理内存里的一段连续数据。链表插入核心是“改指针”。链表并不要求元素在内存里挨着它只要求每个节点记住下一个节点的地址。插入一个节点本质上就是让前驱节点的 next 指向新节点让新节点的 next 指向原来的后继节点。问题来了现实中我们习惯的思维是“下标”是“连续空间”是 index 几就是第几个位置。但链表没有下标你只能从 head 开始一个 next 一个 next 地走。很多同学写链表代码卡住不是 Java 语法不熟而是脑子里还在用数组那套“整体挪动”的图景去套链表。我经常用排队来比喻数组是一排固定座位有人插队后面所有人都得挪一个位子链表是一列手拉手的人新来的人先把手搭在后面那个人肩上前面那个人再把手松开搭到新人肩上队列整体没动只是两个人的手换了个方向。1.2 三条铁律新节点先接后继前驱再断开size 别忘不管头插、尾插还是任意位置插插入动作的内核只有三步新节点的 next 指向目标位置的后继节点前驱节点的 next 指向新节点size 加一。为什么顺序必须是“新节点先接后继前驱再断”因为单链表只有一个方向。假设链表现在是 A-B-C想在 A 和 B 之间插 X。如果先执行 A.next X那 A 的 next 就从 B 变成了 X链表变成 A-X后面的 B-C 就断掉了整个链表后半截找不到了。先执行 X.next B链表暂时还是 A-B-C多了一个 X 指向 B 的分支但没断开任何东西。再执行 A.next XA-X-B-C 完整成型。很多同学第一次写链表反转失败九成都是这个顺序写反了。第三条 size 加一容易被忽略。size 如果没维护好后面 addAtIndex 的越界判断会错get 方法也会错整个类的行为就开始飘。这是我在代码评审里见过次数最多的问题没有之一。把这三条记住后面三种插入方法你看代码就不会懵了。因为头插、尾插、任意位置插入的差别归根结底只有一件事确定前驱节点是谁。2. 地基别歪Node 节点和链表类怎么设计才顺手2.1 Node 为什么敢在类里引用自己单链表的最小单位是一个节点Java 里通常写成一个静态内部类或者独立类。public class Node { public int data; public Node next; public Node(int data) { this.data data; this.next null; } }很多人第一次看到 Node 类里有个 Node 类型的 next 字段会有点懵类还没定义完怎么就在自己内部引用自己了这里的关键是Java 中对象字段保存的是引用也就是地址。next 不保存“一个完整的 Node 对象”只保存“另一个 Node 对象在内存中的地址把”。所以它不会无限递归内存里就是一个节点指向另一个节点的地址链条。这也是链表里“自引用结构”这个说法的来源。现实中排队的人不需要知道整支队伍只需要知道背后那个人是谁队伍信息就不会丢。2.2 链表类字段head 与 size 各管什么事有了 Node还需要一个链表外壳类来管理这些节点。最朴素的做法public class SingleLinkedList { private Node head; private int size; public SingleLinkedList() { this.head null; this.size 0; } public int size() { return size; } public boolean isEmpty() { return size 0; } }head 指向第一个有效节点。空链表时 head 是 null不是指向某个特殊节点。这个设计是最直白的后面任意位置插入时需要在 index 为 0 的特殊情况下单独判断。size 这个字段必须要有。如果没有它任意位置插入时没法判断 index 是否越界只能每次遍历去求长度那样 addAtIndex 本身就 O(n)。为了能在 O(1) 时间内拿到链表长度我建议从一开始就维护 size。这个字段的成本只有每次插入和删除时做一次自增或自减收益是全类的方法都能用到。2.3 用 int 还是泛型练习和工程怎么选练习和面试手写时直接用 int 最好代码量最少注意力能全放在指针操作上。工程上通常是泛型版本public class NodeT { public T data; public NodeT next; public Node(T data) { this.data data; this.next null; } }泛型的坑主要是两个基本类型不能直接用得写 Node 取数据时可能拿到 null要小心空指针。刷题阶段我建议先用 int等三种插入都写熟了再改成泛型体会一下差别。还有一点Node 的字段用 public 在内部实现里完全没问题因为 Node 类是链表类的内部实现细节外部只接触 addAtHead、addAtTail、addAtIndex 这些方法。不必担心封装性被破坏。3. 头插法四行代码里的空表与逆序逻辑3.1 代码和执行顺序头插法的定义是新节点插到链表最前面新节点成为新的 head。代码非常短public void addAtHead(int val) { Node newNode new Node(val); newNode.next head; head newNode; size; }执行顺序拆开看假设当前链表是 2-3要插入 1创建节点 1它的 next 暂时是 nullnewNode.next head节点 1 的 next 指向 2此时链表还是 2-3但节点 1 已经“搭上”了 2head newNodehead 从 2 变成 1size。最终链是 1-2-3完成。3.2 新手最容易写反的两行头插法的核心顺序是“先让新节点指向旧 head再让 head 指向新节点”。我见过最经典的错误写法是这样的head newNode; // 先把 head 换成新节点 newNode.next head; // 再让新节点指向 head这两行一旦执行问题就大了。第一步 head 指向 newNode第二步 newNode.next 指向 head而 head 此时就是 newNode 自己相当于 newNode.next newNode自己指向自己链表从起始位置就形成一个环。后面的节点全部“断开”遍历时死循环。有同学问既然 head 会被 newNode 覆盖为什么不先备份一下旧 head 再赋值备份确实可以Node oldHead head; head newNode; newNode.next oldHead;这个写法也能跑通但它没有“先接后继再断前驱”来得直观而且代码多一行。我更推荐记住铁律newNode.next 永远先赋值head 永远后动。这个顺序在任意位置插入时同样适用。3.3 空表为什么不用判空头插法最爽的一点是空表不用特判。因为空链表时 head 是 nullnewNode.next head 执行完newNode.next 就是 null新节点变成唯一节点然后 head newNode。如果在空链表上用头插newNode.next nullhead newNode链表从空变成只有一个节点完全正确。对比 tail 插法空表必须特判否则 null.next 直接空指针。这一点区别值得记住面试时没必要自己给自己加边界分支。3.4 头插法就是反转链表的底子头插法的另一个身份是“逆序构建器”。你连续用 addAtHead 插入 1、2、3最终链表顺序是 3-2-1因为每次新来的都压在头上。利用这个特性反转链表可以写成这样public Node reverseList(Node head) { Node resultHead null; Node cur head; while (cur ! null) { Node nextTemp cur.next; // 先保存后面 cur.next resultHead; // 当前节点头插到结果链 resultHead cur; // 结果链头前移 cur nextTemp; // 继续原链 } return resultHead; }这里面的关键步骤 cur.next resultHead 和 resultHead cur本质就是 addAtHead 里的两行。所以很多同学背反转链表代码背不下来是因为没看出来这就是头插法。看出来了这题闭着眼都能写。头插法也有坑想顺序构建链表时一定别用头插。比如你要构建一个 1-2-3 的链表用 addAtHead(1); addAtHead(2); addAtHead(3)结果是 3-2-1。我见过有同学真的在循环里用头插顺序添加然后排查半天。头插适合“逆序构建”不适合“顺序构建”。4. 尾插法从每次走到底到维护一个尾巴4.1 最直觉版找到最后一个节点再挂上去尾插法的目标是把新节点挂到链表末尾。没有尾指针的情况下只能从 head 出发一路 next 到最后一个节点然后在它后面接上新节点。public void addAtTail(int val) { Node newNode new Node(val); if (head null) { head newNode; } else { Node cur head; while (cur.next ! null) { cur cur.next; } cur.next newNode; } size; }空表必须特判如果 head 为 null直接让 head 指向新节点。否则走到 else 分支head.next 就是空指针。循环条件为什么是 cur.next ! null 而不是 cur ! null因为我们要找的是“最后一个节点”它的特征是 next 为 null。如果写成 while (cur ! null)循环结束时 cur 已经是 null你就丢失了前一个节点新节点没地方挂。这两个循环条件之间的区别是链表遍历里最容易被忽略的细节。找节点本身用 cur ! null找前驱或最后一个节点用 cur.next ! null。4.2 为什么尾插慢以及完备尾指针版本单链表只有一个方向每次找最后一个节点都要从头走一遍所以无尾指针的尾插是 O(n)。如果连续插入 n 次总耗时就是 O(n^2)。数据量小感觉不出来到几万级别就会肉眼可见地慢。要优化最直接的做法是增加一个 tail 字段始终指向最后一个节点。public class SingleLinkedListWithTail { private Node head; private Node tail; private int size; public SingleLinkedListWithTail() { this.head null; this.tail null; this.size 0; } public void addAtTail(int val) { Node newNode new Node(val); if (tail null) { head newNode; tail newNode; } else { tail.next newNode; tail newNode; } size; } }有了 tail 之后插入新节点只需要tail.next newNode然后 tail 前移一步。不管链表多长都是 O(1)。空表时的处理从 head 特判变成了 tail 特判。tail 为 null 意味着链表为空此时 head 和 tail 都要指向新节点因为链表只有一个节点时它既是头也是尾。4.3 尾指针不是白拿的删除场景下的维护成本tail 的代价在哪里在于删除。删除尾节点时你无法通过 tail 直接找到倒数第二个节点因为单向链表没有 prev。唯一办法是重新从 head 走到倒数第二个节点然后把它的 next 置空。这个操作本身 O(n)而且很容易忘记更新 tail。所以别把 tail 想成万能药。如果业务场景主要是头插、头删或者主要从头部操作tail 就是多余的风险。如果是做 FIFO 队列入队发生在尾部、出队在头部tail 就非常值。我自己的经验是先问自己链表的主流操作是什么再决定要不要加 tail 字段别提前设计。单链表删除尾节点的经典代码提醒一句public void removeLast() { if (head null) return; if (head.next null) { head null; tail null; size--; return; } Node cur head; while (cur.next.next ! null) { cur cur.next; } cur.next null; tail cur; size--; }这里能够明显看到删除尾节点找前驱的过程就是 O(n)。维护 tail 并没有让删除变快反而让更新 tail 这件事成为新的出错点。4.4 FIFO 场景与 ArrayList 的对比尾插法最常见的应用是实现队列的入队操作。队列要求先进先出所以出队在 head 侧入队在 tail 侧。ArrayList 做尾部 add 大部分时候也是 O(1)因为扩容频率低均摊下来很快。但链表队列的好处是每次操作都是真正的 O(1)不会出现数组扩容时一次性搬运大量元素的抖动。而且在元素需要频繁从头部移除的场景里ArrayList 的 remove(0) 是 O(n)因为后面全部要前移链表队头出队是 O(1)。所以选型完全取决于实际数据规模。现在回到标题本身我们最终要掌握的其实是不依赖 tail 的基础版尾插法因为它是理解链表遍历的入口。tail 优化只是在这个基础上加了一个字段逻辑并不复杂。5. 任意位置插入index、for 循环与哨兵节点的三角关系5.1 index 的合法范围0 到 size含头也含尾任意位置插入需要先想清楚 index 的合法范围。数组下标是 0 到 size-1但链表插入位置可以是 0 到 size。为什么是 size因为插入新节点后链表会多一个节点新节点可以出现在最前面、中间、或者末尾。插入到末尾index 等于当前 size。举个例子链表 1-2-3size3你可以插到下标 3也就是 3 的后面这是合法的尾插。所以开头的校验是if (index 0 || index size) { throw new IllegalArgumentException(index 越界: index); }小于 0 不合法大于 size 不合法等于 size 合法。5.2 核心代码为什么边走 index-1 而不是 index处理完边界核心逻辑就是一前一后两个场景先摘掉再走循环找前驱。我直接给出完整版本public void addAtIndex(int index, int val) { if (index 0 || index size) { throw new IllegalArgumentException(index 越界: index); } if (index 0) { addAtHead(val); return; } if (index size) { addAtTail(val); return; } Node newNode new Node(val); Node cur head; for (int i 0; i index - 1; i) { cur cur.next; } newNode.next cur.next; cur.next newNode; size; }这里最核心的是循环里为什么要走到 index-1 这个节点而不是 index 这个节点。因为插入动作修改的是“目标位置前驱节点”的 next。假设链表 1-2-3size3要把 4 插到下标 1也就是让链表变成 1-4-2-3。下标 1 的节点是 2它的前驱是下标 0 的节点 1。我们要做的是让节点 1 的 next 指向 4让 4 的 next 指向 2。所以 cur 必须停在下标 0 的节点上。cur 从 head 出发走 index-1 步正好到下标 index-1 的节点。比如 index1走 0 步cur 就是 head即节点 1。这是对的。如果错写成 i index那 cur 会走到下标 index 的节点也就是目标位置的节点本身。在上面例子里cur 会走到节点 2然后 newNode.next cur.next新节点插到 2 后面变成了 1-2-4-3位置完全偏移一位。这是写任意位置插入最容易踩的坑没有之一。我把最容易混淆的两个 for 边界整理成了对比目标循环条件循环结束时 cur 所在位置找到 index 下标的节点i indexcur 下标 index 的节点找到 index 位置的前驱i index - 1cur 下标 index-1 的节点数组思维会让人下意识走 index 步链表思维要求人清楚“我要修改谁的 next”后者才是关键。5.3 哨兵节点dummy head把头插也变成普通插入上面代码里 index 0 要单独调 addAtHead这个特殊分支的来源是头插时插入位置没有前驱节点。如果你真的不想写这个分支可以用哨兵节点。哨兵节点也叫 dummy head是一个不存业务数据的节点永远站在链表最前面真正有效数据从 dummyHead.next 开始。public class SingleLinkedListWithDummy { private Node dummyHead; private int size; public SingleLinkedListWithDummy() { this.dummyHead new Node(-1); this.size 0; } public void addAtIndex(int index, int val) { if (index 0 || index size) { throw new IllegalArgumentException(index 越界: index); } Node prev dummyHead; for (int i 0; i index; i) { prev prev.next; } Node newNode new Node(val); newNode.next prev.next; prev.next newNode; size; } }这里有个细节有了 dummyHead 之后循环条件是 i index 而不是 i index - 1。为什么因为 prev 的起点从 head 变成了 dummyHeaddummyHead 相当于下标 -1 的节点。prev 走 index 步正好落在下标 index-1 的节点上和上面普通版走到 index-1 是同一个位置。举个例子index0 时循环不执行prev 就是 dummyHead新节点插在 dummyHead 后面恰好就是链表头部。indexsize 时prev 会走到原来的 tail新节点挂在最后。神奇的是有了这个假头头插、尾插、任意位置插变成了同一个方法不再需要任何特判。哨兵节点的代价是head 字段不再存在对外遍历要从 dummyHead.next 开始打印链表时要跳过 dummyHead。但换来的是边界逻辑大幅减化。LeetCode 上“设计链表”这类题很多高效解法都是用 dummyHead 写的我建议你两种版本都练一遍。5.4 0-based 和 1-based一个容易在深处踩的坑我第一次把“第几个节点”和“下标 index”混在一起写时就出过错。有些教材里定义“在第 position 个节点后插入”position 从 1 开始有些地方定义下标从 0 开始。差一位循环边界全错。统一用数组思维比较安全index 从 0 开始index 指向的是插入后的新节点所在位置。设计自己代码时最好在方法注释里写明“index 从 0 开始允许 index size”。这个注释在面试时也能提醒自己别写偏。6. 光会写不叫会边界用例、复杂度账和实战建议6.1 测试用例清单和 toString 验证三种插入写完之后最有效的验证方式不是看代码而是跑一张覆盖边界的测试表。我自己的测试顺序固定如下测试场景操作期望结果空链表头插addAtHead(1)1空链表尾插addAtTail(1)11-2 头插addAtHead(0)0-1-21-2 尾插addAtTail(3)1-2-31-2-3 中插addAtIndex(1, 4)1-4-2-3尾部位置插入addAtIndex(3, 5)1-2-3-5越界负数addAtIndex(-1, 1)抛 IllegalArgumentException越界过大addAtIndex(4, 1)抛 IllegalArgumentException连续头插addAtHead(1), addAtHead(2), addAtHead(3)3-2-1连续尾插addAtTail(1), addAtTail(2), addAtTail(3)1-2-3跑这些测试前我会先给链表类加一个 toString方便肉眼核对输出public String toString() { StringBuilder sb new StringBuilder(); Node cur head; while (cur ! null) { sb.append(cur.data); if (cur.next ! null) { sb.append( - ); } cur cur.next; } return sb.toString(); }toString 本身也是链表遍历的标准写法一次写好后面所有测试都用得上。6.2 复杂度对比慢的是找位置不是改指针三种插入的复杂度可以看这张表插入方式需要找位置吗时间复杂度空间复杂度头插法不需要O(1)O(1)尾插法无尾指针遍历到尾节点O(n)O(1)尾插法维护尾指针不需要O(1)O(1)任意位置插入遍历到前驱节点O(n) O(1)O(1)这张表里最有价值的点是最后一行链表插入那一步修改指针的操作本身是 O(1)真正 O(n) 的是“找前驱节点”的遍历过程。这跟数组插入的 O(n) 有本质区别。数组插入 O(n) 是因为要移动内存中的整段数据链表插入 O(n) 是因为要先从头走一遍找到插入位置。面试里如果你能把这个区别说清楚会显得真的懂链表而不是背过结论。如果追求极端性能头插真的最好不用找任何位置O(1) 搞定。这也是为什么某些栈实现用链表做头部操作。6.3 给新手和面试准备的检查清单最后一条实战建议写给马上要去面试或者第一次刷链表题的人。第一每次写完插入方法立刻问自己三个问题空链表插入会不会空指针插入位置在头尾时会不会丢节点size 是否正确维护这三个问题覆盖了链表题 80% 的边界错误。第二遇到 NullPointerException优先怀疑“循环多走了一步”。for 边界写成 i index 但实际应写 i index - 1或者反过来是链表代码空指针的第一大来源。排查时不用死盯代码在纸上画出链表把 cur 每一步走到哪里标出来很快就能定位。第三面试时先和面试官确认 index 的语义。直接问“index 从 0 开始对吧”这句话不丢人反而说明你考虑问题细致。很多题目模板里 index 的定义不同默认用数组下标思维往往是对的但确认一下最稳。我的个人习惯是链表题先用纸笔画一遍“前驱、后继、新节点”三个节点之间的关系标清楚哪一条箭头的 next 先改然后再写代码。这个习惯帮我省掉了大量 debug 时间。三种插入操作看着简单但它们确实值得反复手写到条件反射因为后面所有链表复杂问题拆到最底层都是这几行指针操作在组合。
