几年前面试Java岗位面试官在纸上画了个方框让我手写单链表的反转。当时我觉得自己把“链表嘛就是节点串节点”背得滚瓜烂熟结果一落笔就露馅了边界条件漏判、循环条件写错、反转完头指针不知道指到哪。那次经历让我意识到java数据结构基础里链表这块光靠“看懂”远远不够必须亲手实现过才能应付面试题和实际项目。这篇博文不端着架子讲道理就围绕Java语言把链表掰开揉碎讲清楚先从底层结构拆解节点和指针的关系再带你手写一个能用的单链表然后把反转、合并、快慢指针这些高频操作逐个过一遍最后聊一聊实际开发里链表相关的坑。适合刚学Java数据结构的新手也适合准备Java后端面试、想在“手撕链表题”环节不翻车的同学。全文代码基于Java 8及以上版本IDE用IDEA最顺手但没有也没关系纯命令行javac一样能跑。1. 先聊清楚为什么数组都带队了链表还是绕不开1.1 数组的“不舒服”和链表出现的理由Java里数组很好用按下标访问元素是O(1)这是它的招牌优势。但数组有两个让人头疼的毛病第一长度固定一旦初始化就不能变想扩容得新建一个更大的数组再copy第二在中间插入或删除元素需要把后面的元素整体往后挪或往前挪最坏情况是O(n)的时间开销。链表就是冲着这两个问题来的。它不要求内存连续每个节点存一份数据外加一个指向下一个节点的引用通过这种“指针串起来”的方式插入和删除只需修改相邻节点的引用指向不用搬动数据本体。当然天下没有免费的午餐链表牺牲了随机访问能力想找第k个元素只能从头一个个走过去。说句实话日常业务开发里数组和ArrayList用得比链表多得多因为大多数场景就是“存一批数据然后遍历”数组更友好。但链表依然是绕不开的知识点原因很现实Java源码里到处都是链表结构——HashMap在哈希冲突时用链表或红黑树存数据LinkedList本身就是双向链表ConcurrentHashMap等并发容器底层也多处涉及链表操作。你读源码、排查问题、做性能优化时不懂链表就寸步难行。1.2 链表到底解决什么问题如果你第一次接触链表可以把它理解为“一列火车”。火车每节车厢装货车厢之间靠挂钩连接车头就是头节点。想在中途加一节车厢只需要解开两节车厢之间的挂钩把新车厢挂进去再连上后面那节前后车厢里的货根本不用搬。这个过程对应到Java代码里就是修改两个节点的next引用。链表解决的核心问题就这么几个动态扩容不用预知数据总量想加多少节点就加多少内存随用随分配。频繁插入删除在已知位置比如在某个节点之后插入或删除时间复杂度是O(1)只要改引用不用像数组那样大面积移动元素。内存碎片化利用内存不连续也有办法串起来充分利用零散空间。那链表有没有劣势太明显了——查找慢按值搜索时平均要遍历一半的节点O(n)缓存不友好节点在内存里东一个西一个CPU缓存命中率低还有额外的指针开销每个节点多存一个或两个引用。我给你的建议很简单别管网上说“链表效率高”还是“链表没什么用”面试和考试就按上面这张图去理解它回答了“为什么需要链表”的本质问题。2. 链表的底层结构拆解Node节点、指针和三种形态2.1 一个Node节点就是一次“定义”很多人学链表卡在第一行代码怎么定义一个节点其实很简单节点就是两个东西的组合——你要存的数据加上指向下一个节点的引用。在Java里通常用一个静态内部类或单独一个类来表示。public class ListNode { // 数据域 public int val; // 指针域指向下一个节点 public ListNode next; public ListNode() {} public ListNode(int val) { this.val val; } }这里的next就是所谓的“指针”Java里不叫指针叫引用它存的是另一个ListNode对象的内存地址。这个类看起来空空的但它就是链表的基石。你往里面塞数据串起来就形成了链表。有人问为什么数据域一般用int能不能放对象当然能ListNodeT泛型化之后就什么都能存了。但面试和学习阶段用int最直观先把逻辑理清楚后面再上泛型。2.2 单链表、双向链表和循环链表一次搞清链表不是一个东西是一个家族。最常见的三种形态我按“车厢挂钩”的思路给你拆开讲。单链表每个节点只知道自己后面是谁不知道自己前面是谁。这就好比一列车只能从车头往车尾方向走你想回头只能从头再来一遍。单链表的节点代码就是上面的ListNode只有一个next指针。它的优点是省内存缺点是删除某个节点时你拿不到它的前驱节点得从头遍历找到前一个节点再改引用。双向链表每个节点多了一个prev指针知道自己的前一个节点是谁。Java的LinkedList底层就是这个结构正因为有prev它做某些操作比单链表方便得多比如反向遍历、删除指定节点直接通过prev找到前驱。代价是每个节点多一个引用内存开销更大。public class DoublyListNode { public int val; public DoublyListNode prev; public DoublyListNode next; public DoublyListNode(int val) { this.val val; } }循环链表表尾节点的next不再是null而是指回头节点形成一个环。循环链表适合“转圈”的应用场景比如操作系统的进程调度、约瑟夫环问题。它有个好处从任何一个节点出发都能遍历完整条链。代价是如果循环条件写不好遍历时容易死循环这点后面专门展开。2.3 哑节点dummy node一个低调但好用的技巧很多链表代码里会看到一个特殊节点它的val没有实际意义但它的存在让代码少了不少边界判断这个节点就是头节点dummy node。举个例子你想在一个单链表的头部插入新节点如果不带头节点你得把新节点的next指向原来的head然后把head指向新节点。但如果你要删除头节点麻烦就来了你直接让head指向head.next即可可如果你要统一“找到前驱节点再删除”的逻辑头节点没有前驱得单独写if判断。如果用哑节点链表永远有一个“假头”顶在前面真实节点从它后面开始。这样所有插入删除的逻辑可以统一处理不需要特判。我在手写链表算法时经常先new一个dummy节点最后返回dummy.next这个技巧在处理“删除倒数第n个节点”“合并有序链表”等题目时尤其好用。3. 手写一个能用的单链表增删改查完整实现这一节是全文的重头戏我会带你从零手写一个单链表。不走捷径不用Java内置的LinkedList因为手写一遍之后你对链表指针的掌控感会完全不同。3.1 定义链表类和初始化先定义一个MyLinkedList类用头节点head表示链表的起始位置用一个size变量记录长度。有了size很多边界判断会简单很多。public class MyLinkedList { private ListNode head; // 链表头节点 private int size; // 链表长度 public MyLinkedList() { head null; size 0; } // 内部节点类 private static class ListNode { int val; ListNode next; ListNode(int val) { this.val val; this.next null; } } }这里我把ListNode定义成静态内部类因为内部类不需要访问外部类的实例字段。这个类目前还干不了任何事接下来一步步往里加方法。3.2 遍历打印链表的基本功遍历是最基础的操作也是后面所有复杂操作的地基。思路就是从头节点开始不断往下移动引用直到碰到null为止。public void printList() { ListNode cur head; while (cur ! null) { System.out.print(cur.val); if (cur.next ! null) { System.out.print( - ); } cur cur.next; } System.out.println(); }你需要注意cur cur.next这行链表遍历的灵魂就在“把当前引用移到下一个节点”。很多人写链表代码时卡住就是因为只知道用cur去访问节点忘记了更新cur本身导致循环卡死在原地。3.3 头插法和尾插法两种插入的边界处理头插法把新节点插到链表最前面。核心步骤是新节点的next指向原来的head然后head指向新节点。顺序一定不能反反了就会丢链。public void addFirst(int val) { ListNode newNode new ListNode(val); // 先让新节点指向原来的头节点 newNode.next head; // 再把头节点更新为新节点 head newNode; size; }这个代码里有个坑很多人第一次写时习惯写head.next newNode那就大错特错了这样会把原来的整个链表丢掉。记住先挂新钩子再动旧车头顺序反不得。尾插法把新节点追加到链表末尾。对空链表直接让head指向新节点非空链表需要遍历到尾节点让尾节点的next指向新节点。public void addLast(int val) { ListNode newNode new ListNode(val); if (head null) { head newNode; } else { ListNode cur head; while (cur.next ! null) { cur cur.next; } cur.next newNode; } size; }尾插法的代价在这里就暴露了每次都要从头遍历到尾部时间复杂度是O(n)。如果你的业务是频繁往尾部追加数据单链表并不是好选择用双向链表的LinkedList或者直接上ArrayList更合适。3.4 按索引插入在下标面前链表就是“半残疾人”数组按下标插入是在“元素位移”链表按下标插入是在“先走到目标位置附近再改引用”。因为链表没有随机访问能力你要插入到第index个位置只能从头开始走index步。public void addAtIndex(int index, int val) { if (index 0 || index size) { throw new IndexOutOfBoundsException(Index: index , Size: size); } if (index 0) { addFirst(val); return; } if (index size) { addLast(val); return; } // 找到第 index-1 个节点即前驱节点 ListNode prev head; for (int i 0; i index - 1; i) { prev prev.next; } ListNode newNode new ListNode(val); newNode.next prev.next; prev.next newNode; size; }这里最关键的动作是最后两步newNode.next prev.next; prev.next newNode;本质上和头插法的逻辑一模一样只是把“头节点”换成了“任意前驱节点”。从某种角度看链表插入操作的规则从来没变过变的只是“从哪个位置开始串”。3.5 删除节点绕着“前驱节点”做文章单链表的删除有一定迷惑性因为它不能回头。你要删除一个节点必须知道它前面那个节点然后让前驱节点的next越过要删除的节点直接指向后一个节点。public void deleteAtIndex(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(Index: index , Size: size); } if (index 0) { head head.next; size--; return; } ListNode prev head; for (int i 0; i index - 1; i) { prev prev.next; } // 让前驱节点指向被删节点的后一个节点 prev.next prev.next.next; size--; }prev.next.next这行第一次看有点绕拆开看其实很直白prev.next是当前要删的节点prev.next.next是要删节点后面的节点。让prev.next直接指向后面那个被删节点就“脱链”了。Java有垃圾回收机制脱链的节点会自动被回收不需要手动释放内存这一点比C/C省心太多。3.6 查找和修改顺着指针一路走下去查找某个值是否存在或者按下标取节点实现思路都是遍历。这里给出一个按下标获取节点的私有方法供内部使用。public int get(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(Index: index , Size: size); } ListNode cur head; for (int i 0; i index; i) { cur cur.next; } return cur.val; }修改指定位置的值只需要先定位到目标节点然后更新它的val即可不需要改动任何指针。这里有个容易忽略的点你的链表类里有next引用永远不要试图在遍历时修改cur的next否则会把链表改坏。修值就是改val不要顺手乱动引用。4. 链表高频操作的实战套路反转、合并与快慢指针基础增删改查写完之后下面这些才是面试和工程里真正值钱的点。我会把常见的套路拆成“思路代码复杂度”三部分你来一个练一个光看不练是学不会的。4.1 反转单链表三指针法吃透指针变化反转链表是链表面试题里的常客思路可以有很多种迭代三指针法最直观、最好向面试官解释。核心思想是用三个指针分别表示前驱节点prev、当前节点cur、下一个节点next每轮循环把当前节点的next指向前驱然后整体往后移动一步。public ListNode reverseList(ListNode head) { ListNode prev null; ListNode cur head; while (cur ! null) { // 先保存下一个节点防止修改next后找不到后面的节点 ListNode next cur.next; // 把当前节点的指针指向前驱 cur.next prev; // 前驱和当前节点整体前移 prev cur; cur next; } // 循环结束时prev就是原链表的尾节点也是新链表的头节点 return prev; }这段代码里最核心的一点就是cur.next prev之前必须先保存next cur.next。我见过不少人第一次写直接把cur.next改了然后发现后面的节点全丢了因为链表是单向的你丢了next引用后面整条链都找不回来。这个反转操作的时间复杂度是O(n)空间复杂度O(1)非常漂亮。如果你用递归来写代码更短但理解成本更高而且递归会产生额外栈空间对超长链表有栈溢出风险。我建议面试时先用迭代法讲清楚再提一句“递归也能做”看面试官追问不追问。4.2 合并两个有序链表哑节点一出手边界全跑走合并两个升序链表思路很直观两个链表各用一个指针谁的当前值小就往结果链表后面接谁。难点在于处理“头节点不确定”的问题——你不知道结果链表第一个节点是从哪条链来的直接用head维护要多写一堆条件判断。解决方式是引入dummy节点正常往后挂最后返回dummy.next即可。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; } // 有一条链遍历完了直接接上剩下的那条 cur.next (l1 ! null) ? l1 : l2; return dummy.next; }这个代码的巧妙之处在于哑节点把“谁当开头”的烦恼屏蔽掉了剩下的就是一串“比较大小——挂节点——移指针”的循环。最后那行cur.next (l1 ! null) ? l1 : l2把剩余链表整个接上也不需要一个节点一个节点地遍历了。如果面试官问你这版的复杂度你要能立刻答出O(mn)。4.3 快慢指针找中间节点和判断环的通用套路快慢指针的思路特别生活化两个人在环形操场上跑步一个快一个慢只要一直跑下去快的人总能套圈追上慢的人。放到链表里就是这样找中间节点快指针每次走两步慢指针每次走一步快指针走到末尾时慢指针正好在中间。判断有没有环快指针一次走两步慢指针一次走一步如果链表有环两者必然相遇如果链表无环快指针会先一步遇到null。public ListNode middleNode(ListNode head) { ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } return slow; } 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; }快慢指针的空间复杂度是O(1)不用额外开集合就能判断环这在面试中是加分项。需要注意循环条件里的fast ! null fast.next ! null这个空指针判断少写一个都会出问题。比如链表只有两个节点且无环如果只判fast.next ! null第二次循环访问fast.next.next时会直接NPE。5. 链表实操中的痛点死循环、空指针和性能误区5.1 死循环是链表世界的第一大坑链表遍历的终止条件无非两种要么是cur ! null遍历到尾部要么是cur.next ! null遍历到最后一个有效节点。但一旦链表里不小心出现了环或者循环条件是while (cur.next ! null)却没正确移动cur就很容易陷入死循环。更隐蔽的情况是你在反转链表时如果某一步指错了方向链表中间变成了一个环程序不会立刻报错而是在遍历时一直绕圈CPU飙高日志刷屏排查起来很痛苦。我自己的经验是写链表代码之前先在草稿纸上画几个节点的箭头图把每一步的指针变化画出来再回去写代码。眼睛看着代码想象指针跳转不如动手画图来得直观。5.2 空指针新手最频繁的报错来源空指针在链表代码里几乎是“每天遇见”的原因通常是对边界情况没有防御。常见的有三类一是链表的头节点为null你直接访问head.valNPE没跑二是删除最后一个节点时prev.next.next等于访问了空的下一个三是快慢指针中快指针一步跳两步但第二步已经越界。处理空指针没有银弹只能靠习惯性地想想三种特殊情况空链表、只有一个节点、只有两个节点。写完代码后先把这三种情况在心里过一遍再跑测试用例。这习惯对写工程代码也很有用不仅仅是链表题。5.3 性能误区“链表插入快”是有限定条件的很多教程说“链表插入O(1)、数组插入O(n)”这句话容易误导人。仔细看我们上面的实现只有在已经知道前驱节点的前提下插入才是O(1)。如果你只知道要插在某个下标位置插入前还得花O(n)时间去遍历定位总开销还是O(n)。同理删除操作如果没有前驱节点同样得先遍历。所以在真实业务里选数据结构不能听到“链表插入快”就无脑上LinkedList。如果你需要频繁在表头和表尾操作LinkedList确实合适如果你经常按下标访问元素ArrayList远胜于LinkedList。这也是Java官方文档里都建议多数场景下ArrayList更高效LinkedList只用在特定的频繁增删场景。5.4 常见问题速查表症状可能原因排查思路遍历陷入死循环链表成环或循环条件写法错误用一个固定次数打印调试或用快慢指针判断是否有环反转后链表变短中间某个节点next指向了自己画图检查每一步指针变化重点看next是否在修改前被保存输出顺序反了尾插法写成了头插法或插入位置算错重新核对addFirst和addLast的代码逻辑空指针NPE访问了null.next或null.val检查边界条件空链表、只有一个节点、删除最后一个节点删除失败两次删到同一节点删除后索引没同步更新检查删除后是否执行了size--以及调用方是否误传同一索引6. Java的链表家族内置LinkedList与手写实现的对比6.1 从单链表到LinkedList之间缺了什么学完手写单链表之后你去翻Java的LinkedList源码会发现它是一个双向链表而且实现了List、Deque等一堆接口。为什么不直接用单链表因为单链表往前遍历极不方便在删除指定节点时还得从头找前驱双向链表通过prev指针直接回退让很多操作变得更顺手。LinkedList的结构大致是这样有first和last两个指针分别指向头尾节点每个节点Node包含item、next和prev三个字段。它支持从头部、尾部快速插入也能作为双端队列使用。如果你面试时被问到“LinkedList的底层结构”能说出“双向链表 first/last指针 内部类Node”这一层基本就够了。6.2 手写链表和LinkedList怎么选刷题和面试时我强烈建议你手写链表因为面试官想知道的是你对指针操作的理解而不是你会不会用现成的LinkedList。但实际项目开发中没有特殊需求就优先用LinkedList它经过充分测试、性能稳定、接口丰富。说到性能有个点值得展开LinkedList按下标访问元素是O(n)而ArrayList是O(1)。LinkedList在中间插入元素虽然节点插入本身是O(1)但你需要先定位到那个下标整体还是O(n)。所以在大多数业务代码里ArrayList的表现反而更好。我见过不少同事因为“LinkedList插入快”这句话把ArrayList换成LinkedList结果性能反而变差了——因为他们的场景是遍历为主随机访问居多而不是在已知位置频繁插入。6.3 迭代器的fail-fast机制一个容易踩的坑用LinkedList或ArrayList做遍历时如果你在遍历过程中调用了list.remove等方法修改结构通常会抛出ConcurrentModificationException这就是fail-fast机制在起作用。它的原理是集合内部维护一个modCount字段每次结构性修改都会加1迭代器持有起始时的modCount每次检查发现不一致就抛异常。这个坑在“边遍历边删除”的场景里尤其常见。正确的做法是使用迭代器的remove()方法或者先收集要删除的元素遍历完再统一删除。这个问题不只是LinkedList的而是整个Java集合框架的通用约束。面试时被问到集合的fail-fast、fail-safe机制你要能说出这个例子。写在最后的一个小建议相信我链表这玩意儿嘴上说“我懂了”一点用都没有。我建议你找一个晚上关掉所有IDE的代码提示掏一张白纸把单链表的反转、合并、删除倒数第n个节点这三道题从第一个类到最后一个方法全部默写一遍。刚开始可能写得很痛苦指针一多就头晕但等你哪天能背着写出来链表的引用跳转在你脑子里就有画面了。如果真的卡住了别急着翻答案先画图把每一步的箭头都标出来再对着图写代码。这个习惯我一直保持到今天它帮我解决过的不仅仅是链表问题还有各种复杂的树和图结构问题。把链表这几招练熟之后再去碰二叉树、图论你会发现“指针引用来回指”的心智负担一下子轻了很多。