最近在帮几个朋友做Java面试前的突击几乎每次都会聊到单链表。聊着聊着我发现一个规律能清楚讲出ArrayList扩容机制的人不少但能一次性把单链表反转写对的人十个里也就两三个。原因也很简单——平时写业务代码链表出现的频率实在太低了大家都在用ArrayList和LinkedList真正手写Node结点、操作next指针的机会几乎没有。可数据结构的基础又绕不开它尤其是Java这边面试题里单链表的基本操作几乎是必考项。今天的主题就是把单链表的基本操作彻底讲透结点怎么定义、插入删除的指针顺序为什么要那样写、反转和环检测这类高频考点又该怎么一步步推出来。1. 为什么Java业务代码里很少手写链表面试却把它当照妖镜很多初中级开发都有这个困惑我工作三年从来没有自己写过一个链表为什么会有人拿这个来面试这个问题问得其实挺好的因为它背后藏着两件事链表在业务里确实用得少但链表背后的思维模型在系统设计里无处不在。1.1 内存视角下的链表数组是连续快递柜链表是散落的货运单数组在内存中是一段连续的空间就像一排连在一起的快递柜每个柜子编号从0开始想取第5个柜子的件直接按编号走过去就行。链表则完全不是这样它的每个结点散落在内存的不同位置每个结点里除了数据本身还存了一个指向下一个结点的门牌号。数组内存示意 [ 0 ][ 1 ][ 2 ][ 3 ][ 4 ] ← 连续地址随机访问 O(1) 链表内存示意 [ data | next ] → [ data | next ] → [ data | null ] 地址0x10 地址0x88 地址0x33所以链表有一个天然特点它不需要一段连续的空闲内存只要每个结点能找到下一个结点整条链就是完整的。对于内存碎片化严重、或者数据量不确定的场景这个特性有一定价值。但在Java里对象本身就在堆上分配内存模型和C语言那种自己管理内存的情况又不太一样这也是链表在Java业务开发里存在感偏弱的原因之一。1.2 面试考链表实际考的是引用思维面试官让你手写单链表并不是指望你以后用链表写业务而是想看三件事。第一你懂不懂引用。Java没有指针语法但每个对象变量本质上都是一个引用链表操作的核心就是不停地让引用重新指向新的对象。很多候选人写反转链表时逻辑混乱根源就是没把引用赋值这件事在脑子里具象化。第二你具不具备边界意识。链表操作极容易产生空指针、最后一个结点没处理、头结点被弄丢这类问题。一个能把边界条件都想清楚的人写工程代码时也不会差。第三你有没有代码组织能力。先写结点类还是先写方法用迭代还是递归这些选择能反映一个人的编码习惯。所以别把单链表当成一道死记硬背的题它的本质是训练你在一个只有引用连接的世界里精确地移动和修改连接。接下来我就用Java把这件事从头拆到尾。2. 写对链表的第一步把Node类和引用模型搞清楚很多教程上来就丢一个LinkedList实现然后开始讲插入删除读者看得云里雾里。其实单链表的地基是两个东西一个叫Node类一个叫引用模型。这两件事通了后面所有操作方法都是顺水推舟。2.1 内部类写法为什么推荐用静态内部类Java里定义链表的结点类最常见的是写成外部类的静态内部类public class MyLinkedList { // 静态内部类结点定义 private static class Node { int val; Node next; Node(int val) { this.val val; } } private Node head; // 头结点引用 private int size; // 链表的结点个数 }有人会问写成普通的内部类行不行技术上当然能运行但我不建议。非静态内部类会隐式持有外部类的引用也就是说每一个Node对象内部都有一个指向MyLinkedList实例的引用这会造成两个后果一是内存上多了一层无意义的引用链二是如果这个Node被其他对象长期持有外部类对象就永远不会被回收相当于埋了一个内存泄漏的雷。静态内部类就没这个问题它和外部类之间没有隐式关联结构上更干净。刷题时经常看到的public class ListNode { int val; ListNode next; }其实就是这个思路只是它独立成文件而已。2.2 别把引用和对象搞混这是链表学习中最关键的一个认知点。Node head new Node(1);这行代码做了什么在堆上new出了一个Node对象然后head变量保存的是这个对象在堆里的地址也就是引用。你可以把对象理解成一间房子引用就是写着门牌号的小纸条你手里拿着纸条才能找到房子。链表操作里的head head.next;是什么是把head这纸条上的门牌号换成下一个结点的门牌号。原来的头结点如果没有任何引用指向它就会被GC回收或者仍然被其他变量引用着。整个链表操作的思维方式就是不停地换纸条、改纸条而不是真的去移动内存里的数据。理解了这一点后面所有的插入、删除、反转你都可以当作在纸上画箭头、改箭头的过程。2.3 最小可运行的链表骨架构造、打印、长度先写一个最小骨架出来后面所有操作都在这上面扩展。我习惯把打印和求长度这种通用方法顺手写上调试的时候能省很多事。public class MyLinkedList { private static class Node { int val; Node next; Node(int val) { this.val val; } } private Node head; private int size; public MyLinkedList() { head null; size 0; } // 头插法新结点插到最前面 public void addFirst(int val) { Node newNode new Node(val); newNode.next head; head newNode; size; } // 打印整条链表 public void printList() { Node cur head; while (cur ! null) { System.out.print(cur.val - ); cur cur.next; } System.out.println(null); } // 求链表长度 public int size() { return size; } }注意打印方法里我用了一个临时变量cur而不用head去遍历。为什么因为一旦用head遍历链表的头结点就丢了之后想从头再走一遍会直接编译逻辑上就断掉。这是一个很小但很常见的坏习惯养成 遍历用临时变量 的规矩能省下未来很多调试时间。3. 基础操作拆解增删改查的指针细节链表的基本操作就是插入、删除、查找、遍历看起来简单但每个操作都有为什么是这样写的逻辑在里面。这里我把它们逐个拆开。3.1 头插为什么O(1)尾插为什么必须遍历头插法只要三步Node newNode new Node(val); newNode.next head; head newNode;把新结点的next指向原来的头结点再把head这个引用指向新结点。整个过程只动了两个引用不依赖链表长度所以是O(1)。尾插法就麻烦一些。如果链表里没有维护tail指针就必须从头开始走到最后一个结点public void addLast(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这时候就不能直接cur.next newNode否则会空指针。所以第一件事就是判断head是否为空。这也是链表操作最常见的边界陷阱——对null调了next。那为什么不建议维护一个tail指针维护了尾插就是O(1)。但代价是插入、删除、拼接操作时都要记得更新tail如果某个操作把尾结点删了你还得重新从head走到新的尾结点去更新tail。这个维护成本很容易在复杂操作里出错。通常算法题里如果没明确要求频繁尾插我就用头插或单独的add方法避免引入额外的状态管理。3.2 指定位置插入的三步法按给定下标插入是链表里的进阶基础操作它的难点在于要在第index个位置插入新结点需要先找到index-1位置的结点。为什么不是找到index位置的结点因为单链表只有next指针你要在中间插入核心操作是修改前一个结点的next所以必须带着前一个结点办事。三步法的示意图插入前 head - 1 - 2 - 3 - null ↑ prev(指向值为1的结点) 要在prev后面插入新结点 new 第一步new.next prev.next; // new 先指向 2 第二步prev.next new; // 1 再指向 new注意顺序不能反过来。如果先把prev.next new执行了链表就变成了head - 1 - new原来的2、3就找不到了new.next也不知道该指向谁整个链就断了。很多人第一次写链表就是栽在这一步上。代码public void add(int index, int val) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index); } if (index 0) { addFirst(val); return; } Node prev head; for (int i 0; i index - 1; i) { prev prev.next; } Node newNode new Node(val); newNode.next prev.next; prev.next newNode; size; }这里index等于0的情况直接复用addFirst是因为头结点没有前驱单独处理会清爽很多。如果你非要把index0也用统一逻辑那就要引入哨兵结点后面会讲否则你会发现for循环里prev prev.next在空链表上直接空指针。3.3 删除操作让前一个结点直接跨过待删结点删除的核心动作是跨过。要删除结点target只需要让target的前一个结点的next指向target的后一个结点删除前 head - 1 - 2 - 3 - null ↑ target 删除后 head - 1 ------ 3 - null代码public boolean remove(int val) { if (head null) { return false; } if (head.val val) { head head.next; size--; return true; } Node prev head; while (prev.next ! null) { if (prev.next.val val) { prev.next prev.next.next; size--; return true; } prev prev.next; } return false; }删除头结点时有一个非常有意思的点head head.next;这行代码执行完后原来的头结点如果没有任何引用指向它就变成了不可达对象等待GC回收。所以在Java里删除不需要你手动释放内存你只要把引用关系剪断GC自然会处理。这在C/C里是不可想象的也是很多从C转Java的人刚开始不太适应的点。而删除中间结点时我用的是prev.next prev.next.next等于让前一个结点跨过了待删结点。这里如果待删结点是最后一个prev.next.next是null赋值后正好把尾结点后的null接上逻辑也没问题。3.4 哨兵结点让边界判断消失一半上面add和remove里都出现了一个恼人的问题头结点没有前驱所以每次都要单独判断index 0或者head.val val。能不能统一处理能用哨兵结点dummy node。哨兵结点是一个不存实际数据、永远固定在链表最前面的哑结点。真实的数据结点从dummy.next开始。这样任何结点包括原来的头结点都有一个前驱了所有插入、删除都可以用统一的循环逻辑不用特判头结点。public class MyLinkedListWithDummy { private static class Node { int val; Node next; Node(int val) { this.val val; } } private Node dummy new Node(0); // 哨兵结点 private int size; public void add(int index, int val) { if (index 0 || index size) { throw new IndexOutOfBoundsException(); } Node prev dummy; for (int i 0; i index; i) { prev prev.next; } Node newNode new Node(val); newNode.next prev.next; prev.next newNode; size; } public boolean remove(int val) { Node prev dummy; while (prev.next ! null) { if (prev.next.val val) { prev.next prev.next.next; size--; return true; } prev prev.next; } return false; } }注意这里遍历的次数变了插入时要走index步而不是index-1步因为prev初始值变成dummy是真实头结点前的一个虚拟位置。LeetCode里大量链表题用dummy node之后代码会清爽一截这个技巧非常值得养成习惯。4. 高频考点逐个图解反转、寻找中点和环检测如果说插入删除是链表的基础那反转链表、找中间结点、环检测就是面试里的必考三件套。这三道题几乎覆盖了链表里最常见的几种思维模型多指针协作、递归思路、快慢指针。4.1 反转链表迭代法题目描述很简单给一个单链表返回反转后的新头结点。比如1-2-3-4-null反转后变成4-3-2-1-null。迭代法的核心是维护三个指针prev前一个已反转好的结点、cur当前要处理的结点、next保存cur原本的下一个结点防止断链。每一步做三件事把cur.next指向prev然后prev和cur同时向后移动。初始状态 null - 1 2 - 3 - 4 - null p c n c.next; // n指向2 第一步 null - 1 - 2 3 - 4 - null p c 第二步 null - 1 - 2 - 3 4 - null p c 继续... 结束 null - 1 - 2 - 3 - 4 p c null代码public ListNode reverseList(ListNode head) { ListNode prev null; ListNode cur head; while (cur ! null) { ListNode next cur.next; // 先保存下一个结点 cur.next prev; // 当前结点指向前一个 prev cur; // prev 前移 cur next; // cur 前移 } return prev; // 结束时prev就是新的头结点 }这个代码里最容易忘记的是ListNode next cur.next这一行。因为执行cur.next prev之后cur原来的下一个结点就找不到了你必须提前把它保存到一个临时变量里。这是链表操作中一个非常重要的直觉改一个引用之前先看这个引用指向的对象是否还需要留备份。4.2 反转链表递归法从头理解到尾递归法很多人看一眼就放弃因为总觉得绕。其实它只有一个核心思想假设从第二个结点开始后面的链表已经反转好了我只需要把第二个结点的next指向第一个结点再让第一个结点的next指向null就完成了整条链的反转。public ListNode reverseListRecursive(ListNode head) { if (head null || head.next null) { return head; // 递归出口空链表或只剩一个结点 } ListNode newHead reverseListRecursive(head.next); head.next.next head; head.next null; return newHead; }我来拆一下。以1-2-3-null为例递归调用顺序是reverse(1)发现1.next不是null先调用reverse(2)reverse(2)发现2.next不是null先调用reverse(3)reverse(3)head.next null返回3此时newHead3回到reverse(2)head.next.next head即让3.next 2再让2.next null返回3回到reverse(1)head.next.next head即让2.next 1再让1.next null返回3最终结果3-2-1-null。注意每一步返回的newHead始终是最原始链表的尾结点反转完成后它就是新链表的头结点。递归法写起来一行核心逻辑但有两个隐藏知识点一是递归栈会消耗O(n)的额外空间对特别长的链表可能栈溢出二是它的代码可读性对很多同事来说不如迭代直观。所以面试时我更推荐你首先写迭代法如果面试官追问还有没有别的思路再抛出递归法并顺带说明它的空间复杂度更高这样反而显得你对复杂度有意识。4.3 快慢指针的两个经典应用快慢指针是链表题里一个看着很神奇想想又很合理的技巧。第一个经典应用找链表的中间结点。定义两个指针slow和fast都从head出发slow每次走一步fast每次走两步。当fast到达链尾时slow正好在中间位置。起点 slow - 1 - 2 - 3 - 4 - 5 - null fast - 1 第一步后 slow - 2 - 3 - 4 - 5 - null fast - 3 - 5 - null 第二步后 slow - 3 - 4 - 5 - null fast - 5 - null fast到尾部 slow正好是3也就是中间结点。代码public ListNode findMiddle(ListNode head) { if (head null) { return null; } ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } return slow; }为什么快指针走两步慢指针走一步最后slow就是中间因为fast的速度是slow的两倍相同时间内fast走的距离是slow的两倍当fast走完全程slow正好走了半程。这个原理不仅适用于找中点还适用于判断回文链表、合并有序链表时找拆分点等场景。第二个经典应用找倒数第K个结点。思路是让fast先走K步然后slow和fast一起走当fast到null时slow就是倒数第K个。这相当于制造了一个长度为K的卡尺slow和fast之间始终保持K的差距。public ListNode findFromEnd(ListNode head, int k) { ListNode slow head; ListNode fast head; for (int i 0; i k; i) { if (fast null) { return null; // k 超过链表长度 } fast fast.next; } while (fast ! null) { slow slow.next; fast fast.next; } return slow; }这里要注意for循环里的判空。如果k比链表长度还大fast会提前变成null不判断的话后续fast.next就空指针了。很多人在这个题上翻车都是因为只写了for (int i 0; i k; i) { fast fast.next; }忽略了非法输入。4.4 检测环与寻找环入口链表中存在环指的是某个结点的next指向了链表中之前的某个结点形成了一个环形回路。判断有没有环最经典的是Floyd判圈算法也就是快慢指针。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; }简单解释为什么能相遇假设链表中有环当slow进入环后可以看作fast和slow都在环形跑道上fast比slow快一个结点的速度每次循环都会把距离缩短1所以迟早会追上slow。如果链表无环fast会先走到null。如果要进一步找到环的入口结点需要用到另一个结论当slow和fast第一次相遇时把其中一个指针移回head另一个保持在相遇点然后两个指针都每次走一步它们再次相遇的位置就是环入口。这个结论可以用路程等式推导这里不展开数学证明只给结论和代码public ListNode detectCycle(ListNode head) { ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { slow head; while (slow ! fast) { slow slow.next; fast fast.next; } return slow; } } return null; }我自己刚学这个结论时也觉得很玄但推导一遍后发现本质就是起点到环入口的距离和相遇点到环入口的距离存在某种相等关系。面试时如果你能把这个结论的推导思路讲清楚面试官对你的印象会明显加分因为它说明你不是背题而是理解。5. 回到Java本身LinkedList源码教会我的事聊完原理回到Java开发者的日常。JDK已经提供了一个现成的LinkedList类很多人直接用但从来没看过它的代码。我强烈建议你去看一眼只看两个点一是它的结点结构二是它的add/remove实现。看完你会发现原来那些链表操作要注意的点在源码里都有体现。5.1 LinkedList不完全是单链表JDK里的LinkedList是基于双向链表实现的它的每个结点除了data和next还有一个prev指向前一个结点。private static class NodeE { E item; NodeE next; NodeE prev; Node(NodeE prev, E element, NodeE next) { this.item element; this.next next; this.prev prev; } }因为有了prev指针它可以从两个方向遍历可以做getLast()、descendingIterator()这种操作。它内部还维护了first和last两个结点引用所以头插和尾插都是O(1)。这跟我们前面写的单链表不太一样单链表为了简化没有prev没有tail代价就是很多操作需要从头遍历。理解这种用空间换时间的取舍非常关键。5.2 和ArrayList的时间复杂度对比面试里高频问题之一就是ArrayList和LinkedList有什么区别。只看时间复杂度的话操作ArrayListLinkedList随机访问 get(i)O(1)O(n)头部插入 addFirstO(n)需要移动元素O(1)尾部插入 addLast均摊O(1)O(1)中间插入 add(i)O(n)移动后半段O(n)找到位置内存占用连续空间可能预留容量每个结点额外存next/prev引用看似LinkedList在头部插入上有绝对优势但实际业务里头部插入的场景极少。更关键的是ArrayList在内存中是一块连续区域CPU缓存的局部性远好于LinkedList那堆散落的对象所以实际运行时遍历ArrayList往往比遍历LinkedList快得多。这也是为什么很多Java社区的建议是能用ArrayList就尽量别用LinkedList。5.3 什么场景才该真正使用链表那链表真的没有用了吗当然不是。我做过的项目里链表最典型的应用是LRU缓存。用LinkedHashMap实现LRU很简单但如果你想自己写一个双向链表HashMap就是经典方案HashMap负责O(1)查找双向链表负责维护访问顺序每次访问某个key就把它移动到链表头部缓存满了就淘汰链表尾部。另外像队列这种数据结构LinkedList实现了Deque接口可以用作双向队列在需要频繁在两端插入删除时确实比ArrayList合适。还有像实现撤销功能、浏览器的前进后退都可以借助双向链表的天然顺序感来组织。我的观点是日常开发优先用现成的List接口下的实现但当你真的需要自定义数据结构时理解链表的内存模型和指针操作会让你很有底气。这也是为什么面试官对链表基础格外执着——它检验的不是你会不会调库而是你对程序底层运行逻辑的理解。6. 踩坑复盘那些让我debug到怀疑人生的问题说几个我在写链表时真实踩过、也真实花了很长时间排查的坑。这些坑不写在教科书上但几乎每个手写链表的人都遇到过。6.1 教训一反转后成环遍历死循环的完整排查有一次我写一个反转函数逻辑看起来完全没问题但一运行就死循环。当时的代码大概是这样的public ListNode reverse(ListNode head) { ListNode prev head; ListNode cur head.next; while (cur ! null) { ListNode next cur.next; cur.next prev; prev cur; cur next; } return prev; }初看好像没啥问题但我把prev初始化为head而不是null。这导致整个反转过程多出了一个循环引用。我用一个1-2-3-null的例子跑一遍就能发现初始prev1, cur2, next3 第一步2.next1链表变成了 1 - 2 3-null 第二步3.next2链表变成了 1 - 2 - 3当cur为null退出循环时返回的prev是3看起来好像没问题但实际上原本头结点1的next仍然指向2形成了一个1-2-3-2-3-...的死循环。排查过程是这样的我打印链表时程序卡住不动任务管理器里内存飙升。后来我不打印只输出长度才发现长度永远算不完。最终靠手动走两遍代码才定位到问题——prev的初值错了。这件事给我最大的教训是链表里任何赋值操作都要问自己会不会有两个结点互相指向。互指就是环环就是死循环。6.2 教训二空指针往往不是没有对象而是没连接上学链表的人一定写过这样的报错Exception in thread main java.lang.NullPointerException at MyLinkedList.add(MyLinkedList.java:56)最常见的场景是在空链表上调用head.next。我看到很多人这时候第一反应是哦head是null所以报错了然后给head加上判空。这当然没错但更深层的问题是为什么head会是null很多时候是因为上一次操作里你把head的引用搞丢了。我举一个真实的例子。有次我在写deleteNode方法时用了一个局部变量cur去遍历结果误操作了cur cur.next.next导致链表中间断开但head变量还指着原来的头结点。打印头结点时看着正常一从中间访问就空指针。这种问题靠加判空是解决不了的必须把整个链表走一遍画出每个结点的连接关系才能发现是哪个引用没连上。所以我的建议是遇到空指针别急着补if判断先打印一遍完整的链表结构看看是不是有结点被意外跳过了。6.3 教训三逆序操作后头结点丢失是另一类经典问题反转链表写完返回了新的头结点但外部变量还拿着旧的头结点。很多人写完方法在主函数里还是用原来的head变量去遍历发现只打印出了一个结点然后就开始怀疑反转函数写错了。其实不是。反转后原head已经是尾结点它的next是null所以从头打印只能看到一个结点。正确做法是接收返回值ListNode newHead reverseList(head); printList(newHead); // 用新的头结点这个坑我见过太多人踩了。本质原因是Java的方法传参是值传递不过这个值恰好是引用。你在方法内部重新给head变量赋值不会影响到外部的head变量。所以函数如果需要返回新头结点调用方必须记得接收。6.4 面试写链表我习惯的三个动作最后聊聊面试场景下怎么从容写完链表题。我自己的习惯是第一先在草稿纸上画一条3到4个结点的链表标出head、cur、prev、next这些指针的位置。画完再动手写代码错误率会大幅下降。面试官不会催你那半分钟他们更不愿看到你写一半改半天。第二先写边界条件。空链表、单结点链表、操作头结点这三类情况在链表题里几乎必考。先把它们想清楚再写主逻辑最后回头检查边界你会发现自己写出来的代码稳定很多。第三每写一个赋值语句就问自己一个问题被赋值的next原来指向的对象还有别的引用指着它吗如果没有它会不会在后续操作里被需要这个问题能帮你拦截掉80%的断链错误。链表这东西说白了就是引用游戏。把它当成画画每次改动都画一遍箭头动手写代码前先在脑子里运行几行很多看起来玄乎的问题都会变得非常直观。希望这篇图解能在你刷题或者面试时帮上忙。