写链表是Java面试中几乎绕不开的基础题但很多人在白板上写出来的链表跟真正能用在工程里的链表差距很大。差别往往不在算法本身而在一个看似不起眼的设计——头结点dummy head也叫哨兵节点。我这段时间重新梳理数据结构基础用Java从头实现了一遍带头结点的单链表顺手把增删改查、反转以及面试常考的链表中点、回文判断、合并有序链表都串了一遍。这篇文章就把整个过程记录下来重点讲清楚带头结点的设计为什么能省掉大量边界判断以及实现细节里那些容易翻车的点。如果你正在学数据结构、准备Java开发岗面试或者单纯想把手写链表写得更稳这篇可以当一份带注释的参考。1. 带头结点的链表头结点到底解决了什么问题1.1 从一次翻车说起头部插入为什么容易写错很多朋友第一次写单链表大概率会写出这样的结构public class ListNode { int val; ListNode next; ListNode(int val) { this.val val; } }然后链表本体只保存一个head引用。这种写法本身没错但一旦要实现在指定位置插入、删除指定节点麻烦就来了。以最常见的头部插入为例public void addFirst(int val) { ListNode newNode new ListNode(val); newNode.next head; head newNode; // 必须更新 head }这段代码看着不难但如果你同时要实现add(index, val)就会发现index为0的情况必须单独处理if (index 0) { addFirst(val); return; } ListNode cur head; for (int i 0; i index - 1; i) { cur cur.next; } ListNode newNode new ListNode(val); newNode.next cur.next; cur.next newNode;删除头节点的分支更明显if (index 0) { head head.next; // 头节点没有前驱只能直接改 head return; }问题出在哪链表的“第一个真实节点”没有前驱。所有基于“找前驱节点”的插入删除逻辑在第一个节点身上都要退化成另写一套处理逻辑。一旦代码分支多了漏更新head是早晚的事。我自己第一次手写时就翻过车删除头节点后忘了改head然后拿着一个悬空的引用继续遍历直接空指针。1.2 哨兵节点让所有节点都有“前驱”带头结点链表的核心思路很简单在链表最前面固定放一个不存业务数据的节点叫头结点或哨兵节点。真实数据从dummyHead.next开始。这样带来的最大变化是——链表的每一个真实节点都有前驱所有增删逻辑都能统一用prev.next来完成。以头部插入为例用上哨兵后public void addFirst(int val) { ListNode newNode new ListNode(val); newNode.next dummyHead.next; dummyHead.next newNode; size; }注意这里不再需要更新任何“head变量”因为链表入口始终是那个固定的dummyHead。按下标插入时无论index是0还是size逻辑完全一致先走到目标位置的前驱然后改指针。链表是否为空的判断也从head null简化成了dummyHead.next null。我在LeetCode刷合并两个有序链表这类题时也特别喜欢用哨兵节点新建一个dummy作为结果链表的起点最后返回dummy.next全程不需要讨论“结果链表最开始是不是空的”这种边界。可以说哨兵节点是把“特殊处理”翻译成“统一逻辑”的经典设计。提示头结点本身不存放业务数据它的val通常用0或null初始化真正的目的是让代码结构统一。面试时如果能主动说出“我用头结点来统一插入删除逻辑”通常是个加分点。2. 用Java手写一个带头结点的单链表核心代码拆解2.1 节点类与链表类的骨架设计为了代码简洁先用int作为存储类型理解核心逻辑后想做成泛型也容易把int替换成E再给链表类加上E声明即可。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; } }链表本体类public class SinglyLinkedList { private final ListNode dummyHead new ListNode(); private int size; public SinglyLinkedList() {} public int size() { return size; } public boolean isEmpty() { return size 0; } }两个地方解释一下。第一dummyHead声明为final。因为我们从头到尾只操作dummyHead.next不会用一个新节点替换头结点本身final能防止无意间破坏这个哨兵。第二size字段非常重要。链表的遍历是O(n)如果没有size每次获取长度都得到尾部去数一遍很多方法的边界校验就没法快速完成。增删操作里维护好size后面写add(index, val)、remove(index)时就能第一时间判断下标合法性。2.2 插入操作头插、尾插、按下标插入实现了这三种插入基本就覆盖了单链表插入的全部场景。public void addFirst(int val) { add(0, val); } public void addLast(int val) { add(size, val); } public void add(int index, int val) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } ListNode cur dummyHead; for (int i 0; i index; i) { cur cur.next; } ListNode newNode new ListNode(val); newNode.next cur.next; cur.next newNode; size; }这里有几个细节值得展开。为什么addLast直接调用add(size, val)因为在带头结点的链表中在“末尾”插入新节点等价于在序号为size的位置插入。而add的循环允许index size此时cur正好走到最后一个真实节点cur.next是null新节点接入后正好在末尾。再说按下标插入的核心。很多人第一反应是“我要走到第index个节点”但正确做法是走到第index个节点的前驱。为什么要这样因为单链表只能从前往后走要修改某个节点的后继指针你必须先拿到这个节点的前驱。有了dummyHead之后index0时前驱就是dummyHead自己不需要分支。插入的指针操作顺序也是个经典考点newNode.next cur.next; // 先把新节点的后继接到原链表的后半段 cur.next newNode; // 再把前驱的后继改成新节点顺序反了就麻烦了。如果先执行cur.next newNode原链表后半段就被“丢”了因为cur.next已经被新节点覆盖再想拿cur.next.next指向的后半段拿到的就是新节点而不是原来的后继。我当时学这个的时候老师给的口诀是“先接后断”先接上新节点的next再断开旧连接。画个图一眼就明白。2.3 删除操作按位置删和按值删删除节点的本质也是一样找到目标节点的前驱让前驱的next跳过目标节点。public int remove(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } ListNode cur dummyHead; for (int i 0; i index; i) { cur cur.next; } ListNode target cur.next; cur.next target.next; target.next null; size--; return target.val; } public boolean removeByValue(int val) { ListNode cur dummyHead; while (cur.next ! null cur.next.val ! val) { cur cur.next; } if (cur.next null) { return false; } ListNode target cur.next; cur.next target.next; target.next null; size--; return true; }删除的指针操作比插入简单核心就是一行cur.next target.next;它让前驱节点的next跳过target直接指向target的后继。这里有个小习惯我想推荐删除后顺手把target.next置为null。虽然Java的GC会自动回收不可达对象不置空也能正常工作但显式断开引用能让链表结构在调试时更清晰也避免某些疏忽操作顺着target又摸到原链表里。这个习惯写多了就会觉得“穷讲究”但严谨并没有坏处。按值删除的循环条件也很典型while (cur.next ! null cur.next.val ! val)它同时做了两件事一是确保下一个节点存在二是检查下一个节点的值。这样循环结束后只要cur.next ! null就说明找到了目标而且cur正好是目标的前驱可以直接改指针。如果用while (cur ! null cur.val ! val)退出循环时你找到的是目标节点本身可它没有前驱引用你还是没法删。这就是单链表在结构上的限制。2.4 遍历、获取、修改与反转遍历打印是最直观的调试手段public void print() { ListNode cur dummyHead.next; while (cur ! null) { System.out.print(cur.val - ); cur cur.next; } System.out.println(null); }获取和修改指定位置的元素注意边界判断和从头结点下一个节点出发public int get(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } ListNode cur dummyHead.next; for (int i 0; i index; i) { cur cur.next; } return cur.val; } public void set(int index, int val) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } ListNode cur dummyHead.next; for (int i 0; i index; i) { cur cur.next; } cur.val val; }我自己写的时候会注意一个区别get/set要从dummyHead.next开始走因为下标0指向的是第一个真实节点而插入、删除要从dummyHead开始走因为我们要找的是“目标位置的前驱”。这两个起点选错了结果就会差一个节点。最后是反转链表。这个操作在面试里出场率极高后面也会反复用到public void reverse() { ListNode prev null; ListNode cur dummyHead.next; while (cur ! null) { ListNode next cur.next; cur.next prev; prev cur; cur next; } dummyHead.next prev; }三指针的迭代思路是用prev保存当前节点的前驱用cur遍历原链表用next提前保存当前节点的后继防止改指针后丢失链表。每一步都在做同一件事——让cur.next指回prev把箭头方向调转。循环结束后prev就是原链表的最后一个节点也就是反转后新链表的第一个真实节点把它挂到dummyHead.next上就行。3. 链表操作中最容易翻车的几个细节3.1 遍历终止条件什么时候用cur什么时候用cur.next一提到链表新手问得最多的就是“遍历到底是while (cur ! null)还是while (cur.next ! null)”这两种写法其实对应完全不同的语义用错就会空指针或者漏掉最后一个节点。while (cur ! null)访问每一个节点本身适合打印、统计、查找。while (cur.next ! null)停在最后一个节点上适合“在末尾插入”这种需要定位尾部前驱的场景。比如addLast如果写成while (cur ! null)循环结束后cur变成null你根本不知道最后一个节点是谁就没法接新节点了。反过来如果你遍历打印时用while (cur.next ! null)循环会在最后一个节点停下导致最后一个节点的值没被打印出来。我的经验是写之前先问自己“这条循环结束后我期望cur停在哪个节点上”。如果停不下来就把cur ! null理解成“当前节点还有内容要处理”如果就是要找“最后一个能接新节点的人”用cur.next ! null。一旦想清楚这个很多链表代码的错误都能提前规避。3.2 删除节点后要不要置空next继续说target.next null这件事。有人会觉得这是画蛇添足Java又不是C/C不需要手动管理内存。但实际工程里我依然推荐写理由有三个。第一调试时如果单步走到target上next被截断后IDE的变量面板不会把它身后的整条链表全部展开省得误判。第二如果链表后续被某个缓存结构暂时持有截断引用能让对象更快地满足GC条件虽然极端但聊胜于无。第三这也是代码自注释的一种方式读者看到target.next null会立刻意识到“这个节点已经从链表中摘掉了”。当然如果公司代码规范里统一不写也不影响功能。这是一个“锦上添花”的洁癖我建议保留。3.3 反转链表的递归写法理解head.next.next head面试官经常在看完迭代反转后追问一句“递归怎么写”递归版代码非常短但第一次看到的人往往一脸懵public ListNode reverseRecursive(ListNode head) { if (head null || head.next null) { return head; } ListNode newHead reverseRecursive(head.next); head.next.next head; head.next null; return newHead; }关键在于理解递归的“信任”reverseRecursive(head.next)会返回从head.next开始的链表反转后的新头。你要做的只是把当前节点接到这个已经反转好的链表末尾。那么head应该怎么接原本的链表顺序是head - head.next - ...反转后的顺序应该是... - head.next - head。所以需要让head.next这个节点反转完成后它变成了尾部的next指向head这就是head.next.next head的含义。之后head.next置null因为head是反转后链表的新尾部。如果还觉得绕可以拿长度为2的链表走一遍head1, next2递归到2时直接返回2然后执行1.next.next 1即2.next 11.next null得到2 - 1。递归的妙处在于“不用管中间过程只处理当前层和下一层之间的关系”。3.4 调试链表代码的实用建议链表代码出bug靠眼睛盯代码通常效率很低我的习惯是三步走。第一步画图。任何涉及next修改的操作都先在纸上把节点画成方框把箭头画成连线动手改几个箭头跑通整个流程再写代码。纸上跑不通的代码里大概率也跑不通。第二步边界用例。每个方法写完至少用三种链表测试空链表、只有一个节点的链表、正常长度链表。空链表能查出空指针单节点能查出“头尾不分”的问题正常链表则检验一般逻辑。第三步打印中间状态。在关键循环里临时加一行System.out.println观察cur停在哪里、next被改成了什么。这个方法比断点调试更直观尤其适合初学者。4. 从链表到面试题这些高频考察点如何应对4.1 快慢指针找到链表中点、判断是否有环快慢指针是链表题里最常用的技巧之一。一个慢指针每次走一步一个快指针每次走两步利用速度差来定位中点或检测环。找中点的经典写法ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } // slow 就是链表中点当链表长度为奇数时slow自然落在中间节点偶数时slow落在偏右的那个节点上。这个规律不需要死记你自己拿长度2和长度3的链表模拟两遍就清楚了。为什么fast ! null fast.next ! null因为快指针一次跳两步如果fast已经到达末尾或者只剩一个节点再跳就越界了。判断是否有环的逻辑几乎一模一样public boolean hasCycle(ListNode head) { ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { return true; } } return false; }如果链表存在环快指针最终一定会在环里追上慢指针。想象一下操场跑步速度快的会“套圈”总有一个时刻两个人位置重合。这个题也是面试高频建议和找中点合并掌握。4.2 删除倒数第N个节点双指针的解法很经典让第一个指针先走N步然后两个指针同步前进。当第一个指针走到链尾时第二个指针正好停在“倒数第N个节点的前驱”。public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0); dummy.next head; ListNode first dummy; ListNode second dummy; for (int i 0; i n; i) { first first.next; } while (first.next ! null) { first first.next; second second.next; } second.next second.next.next; return dummy.next; }这个题最大的坑是如果要删除的节点就是原始头节点直接返回head.next会出错。但用了哨兵节点dummy后删除倒数第N个节点变成完全统一的操作不需要额外的if分支。这也是哨兵节点在“看似需要边界判断”时发挥价值的好例子。我在LeetCode上提交这个题时第一次没加dummy结果n等于链表长度时直接越界报错补上dummy后一次通过。4.3 判断回文链表判断一个链表是否回文正读倒读一样是综合题因为至少串联了三个基础操作找中点、反转后半段、逐个比较。public boolean isPalindrome(ListNode head) { if (head null || head.next null) { return true; } ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } ListNode second reverse(slow); ListNode first head; while (second ! null) { if (first.val ! second.val) { return false; } first first.next; second second.next; } return true; } private ListNode reverse(ListNode head) { ListNode prev null; ListNode cur head; while (cur ! null) { ListNode next cur.next; cur.next prev; prev cur; cur next; } return prev; }注意这里反转的是从slow开始的链表。拿链表1 - 2 - 2 - 1为例慢指针走到第三个节点2反转后半段变成1 - 2跟前半段1 - 2逐位比较完全匹配就是回文。这个题的解法不唯一也可以把整条链表反转再比较但那样空间复杂度更高。用“找中点反转后半段”的方式空间复杂度是O(1)正是面试官想听的那个答案。4.4 合并两个有序链表LeetCode 21也是经典的哨兵应用场景。用迭代写法加一个dummy头public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); ListNode cur dummy; while (l1 ! null l2 ! null) { if (l1.val l2.val) { cur.next l1; l1 l1.next; } else { cur.next l2; l2 l2.next; } cur cur.next; } if (l1 ! null) { cur.next l1; } else { cur.next l2; } return dummy.next; }这个题如果用非哨兵思路写第一步就得先判断l1和l2谁的头更小还要处理空链表的情况。而有了dummy我们永远不需要讨论“结果链表是否为空”只需要不断把较小的节点挂到cur.next上。循环结束后把剩余的那条链表整个接上。dummy.next就是合并后的头节点。很多新手会纠结“为什么最后返回的是dummy.next而不是dummy”因为dummy本身不存数据它的next才是第一个真实节点。这个认知建立了以后看很多官方题解都会觉得顺畅很多。5. 带头结点链表的应用场景与性能权衡5.1 链表的适用场景是什么单纯说链表“适合插入删除”还不够准确。更精确地说链表适合在已知前驱节点的情况下进行O(1)的插入和删除以及从头部批量操作的场景。比如哈希表的链地址法解决冲突每个桶挂一条链表新元素直接头插O(1)完成。LRU缓存淘汰双向链表配合哈希表能在O(1)时间内移动一个节点到头部或删除尾部节点。内存分配器中的空闲链表按块大小组织空闲内存分配和释放都涉及链表操作。撤销/重做历史记录双向链表天然支持前进和后退。如果你的业务主要是“尾部追加按下标随机访问”那数组结构的ArrayList几乎是标准答案。链表的随机访问是O(n)在这类场景下没有任何优势。5.2 与ArrayList的性能对比我把两者的关键特性整理成一张表面试时也经常需要说清楚维度数组/ArrayList单链表随机访问O(1)O(n)头部插入O(n)需要搬移元素O(1)尾部插入均摊O(1)O(n)需要遍历到尾部中间插入O(n)O(n)查找前驱O(n)插入O(1)内存连续性连续地址缓存友好离散节点缓存不友好扩容需要动态扩容并搬移天然无扩容注意表格里有一个反直觉的点ArrayList在尾部插入其实很快Java的add(E e)是均摊O(1)。而单链表在尾部插入反而需要从头走到尾是O(n)。这就是为什么很多资深开发者会说“LinkedList很多场景下不如ArrayList快”因为就算你在中间插入ArrayList搬移元素的代价在数据量小时未必比链表遍历差加上数组的缓存局部性优势实际表现往往更优。那学习链表还有没有必要当然有。一方面是数据结构思维本身另一方面是很多系统底层和算法题目依然离不开链表。能用好链表的人对“引用”Java里的next就是引用的理解会更深刻这对理解对象引用、内存模型都有帮助。5.3 从单链表到双向链表、循环链表掌握了带头结点单链表之后建议把视野再拓宽一点把三种链表结构放一起对比单向链表每个节点只有next指针只能从头往后走删除指定节点必须知道前驱。双向链表每个节点有prev和next支持反向遍历Java的LinkedList底层就是双向链表。删除时只要拿到节点本身就能通过prev找到前驱。循环链表最后一个节点的next指向头结点或第一个节点适合环形缓冲、轮询调度等场景。循环链表和带头结点结合时哨兵节点的价值更明显头结点的next指向第一个节点最后一个节点的next又回到头结点整个链表形成一个环形结构判断“是否遍历完一圈”只需要看当前节点是否等于头结点。我自己把三种结构都写过一遍之后再回来看LeetCode的hard题比如复制带随机指针的链表、K个一组反转链表思路都清晰很多。链表题的本质永远是“画图、改指针、验边界”这三板斧练熟了什么结构都只是变体。最后分享一个小经验面试前如果只够时间准备一个数据结构我一定选链表。一方面它的代码量小适合手写另一方面它能承前启后——承前是理解对象引用启后是理解树、图的邻接表表示。写链表时多问自己一句“这里的next到底指向谁为什么改了不会丢链”比多背十个API有用得多。