概述为什么链表题容易让初学者卡住学完栈和队列之后我们继续看另一类非常基础、也非常高频的数据结构链表。数组和链表都可以存储一组元素。但它们最大的区别在于数组依靠下标访问元素 链表依靠指针连接元素这也导致链表题和数组题的思维方式很不一样。数组题常常在想下标 i 怎么移动 区间边界在哪里而链表题常常在想当前节点是谁 下一个节点是谁 指针应该先保存还是先修改很多初学者做链表题时最容易出现的问题不是思路完全不会而是指针断了节点丢了循环条件写错返回了错误的头节点忘记处理空链表或单节点链表这篇文章会围绕链表最常见的四个方向展开链表的基本结构与指针操作反转链表合并两个有序链表快慢指针解决中点、环形链表等问题学完这篇你应该能看懂链表指针变化并能独立写出反转链表、合并链表和快慢指针这几类高频题。核心概念链表到底是什么链表是一种由节点组成的数据结构。每个节点通常包含两部分值当前节点存储的数据指针指向下一个节点的位置单链表可以表示成head | v [1] - [2] - [3] - [4] - null在 Java 中常见的链表节点定义如下publicclassListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.valval;}ListNode(intval,ListNodenext){this.valval;this.nextnext;}}其中val表示节点值next表示下一个节点head表示链表头节点如果head null说明链表为空。链表和数组的区别对比项数组链表内存结构连续存储节点分散存储访问元素可通过下标随机访问只能从头逐个遍历查找第i个元素O(1)O(n)插入删除节点可能需要移动大量元素修改指针即可常见考点下标、区间、双指针指针修改、头节点、快慢指针链表最核心的能力不是快速访问而是通过修改指针关系改变节点之间的连接方式。链表题的本质不是操作值而是操作节点之间的next指针。基础操作遍历链表遍历链表是所有链表题的基础。ListNodecurhead;while(cur!null){System.out.println(cur.val);curcur.next;}这里的cur是一个移动指针。它从头节点开始每次移动到下一个节点。遍历过程cur | v [1] - [2] - [3] - null cur | v [1] - [2] - [3] - null cur | v [1] - [2] - [3] - null当cur null时说明已经走到链表末尾。遍历时常见错误错误写法while(cur.next!null){curcur.next;}这个循环会停在最后一个节点而不是遍历所有节点。如果你需要处理每个节点通常应该写while(cur!null){curcur.next;}当然如果题目明确需要停在最后一个节点前面才会使用cur.next ! null。指针操作为什么要先保存后修改链表题最重要的一条经验是修改next指针前先想清楚后面的节点会不会丢。比如有链表1 - 2 - 3 - null如果当前cur指向节点1cur.nextnull;那么节点2和节点3就无法再通过cur找到了。所以在修改指针前通常要先保存下一个节点ListNodenextcur.next;cur.nextnull;curnext;这也是反转链表中最关键的动作。经典题型一反转链表题目给定单链表头节点head请反转链表并返回反转后的头节点。示例输入1 - 2 - 3 - 4 - 5 - null 输出5 - 4 - 3 - 2 - 1 - null解题思路反转链表的核心是把每个节点的next指针反过来。原链表1 - 2 - 3 - null反转后3 - 2 - 1 - null我们使用三个指针prev当前节点反转后应该指向的前一个节点cur当前正在处理的节点next提前保存cur.next防止链表断开后找不到后续节点初始状态prev null cur head每一轮做三件事1. 保存 next cur.next 2. 反转 cur.next prev 3. 两个指针向后移动prev cur, cur nextJava 代码实现classSolution{publicListNodereverseList(ListNodehead){ListNodeprevnull;ListNodecurhead;while(cur!null){ListNodenextcur.next;cur.nextprev;prevcur;curnext;}returnprev;}}执行过程以1 - 2 - 3 - null为例第一轮next 2 1.next null prev 1 cur 2结果1 - null 2 - 3 - null第二轮next 3 2.next 1 prev 2 cur 3结果2 - 1 - null 3 - null第三轮next null 3.next 2 prev 3 cur null结果3 - 2 - 1 - null最后cur null循环结束prev就是新的头节点。复杂度分析时间复杂度O(n)每个节点处理一次空间复杂度O(1)只使用常数个指针反转链表的关键是先保存next再修改cur.next最后移动prev和cur。反转链表的递归写法反转链表也可以用递归完成。递归思路是先反转后面的链表再把当前节点接到反转结果的末尾。代码如下classSolution{publicListNodereverseList(ListNodehead){if(headnull||head.nextnull){returnhead;}ListNodenewHeadreverseList(head.next);head.next.nexthead;head.nextnull;returnnewHead;}}递归代码怎么理解假设链表是1 - 2 - 3 - null递归调用reverseList(2)会把后半部分反转成3 - 2 - null此时head仍然是节点1并且原来的关系还是1 - 2要把1接到2后面需要head.next.nexthead;也就是2 - 1然后断开原来的指向head.nextnull;否则会形成环1 - 2递归写法更简洁但对初学者来说不如迭代直观。刷题时建议先熟练掌握迭代写法。递归复杂度时间复杂度O(n)空间复杂度O(n)递归调用栈占用空间经典题型二合并两个有序链表题目将两个升序链表合并为一个新的升序链表并返回合并后的头节点。示例输入 1 - 2 - 4 1 - 3 - 4 输出 1 - 1 - 2 - 3 - 4 - 4解题思路这道题和归并排序中的合并过程很像。每次比较两个链表当前节点的值谁小就把谁接到结果链表后面对应链表指针向后移动重复直到其中一个链表为空最后把剩余链表接到结果后面这里常用一个技巧虚拟头节点。什么是虚拟头节点虚拟头节点也叫 dummy 节点。它不是最终答案中的真实节点只是为了简化代码。如果不用 dummy就要单独处理第一个节点结果链表头节点到底应该是 l1 还是 l2用了 dummy 后可以统一写成dummy - 已合并部分最后返回dummy.nextJava 代码实现classSolution{publicListNodemergeTwoLists(ListNodelist1,ListNodelist2){ListNodedummynewListNode(0);ListNodecurdummy;while(list1!nulllist2!null){if(list1.vallist2.val){cur.nextlist1;list1list1.next;}else{cur.nextlist2;list2list2.next;}curcur.next;}if(list1!null){cur.nextlist1;}if(list2!null){cur.nextlist2;}returndummy.next;}}为什么最后可以直接接上剩余链表因为两个输入链表本身已经是升序的。当其中一个链表为空时另一个链表剩下的节点也已经有序。所以不需要继续一个个比较直接接到结果链表末尾即可。复杂度分析时间复杂度O(n m)两个链表每个节点最多访问一次空间复杂度O(1)只使用常数个额外指针其中n和m分别是两个链表的长度。虚拟头节点可以统一处理结果链表的连接逻辑避免单独判断新链表头节点。经典题型三删除链表节点删除节点也是链表题中的基础操作。如果要删除某个值等于val的节点常见写法如下classSolution{publicListNoderemoveElements(ListNodehead,intval){ListNodedummynewListNode(0);dummy.nexthead;ListNodecurdummy;while(cur.next!null){if(cur.next.valval){cur.nextcur.next.next;}else{curcur.next;}}returndummy.next;}}为什么删除节点也适合用 dummy如果要删除的是头节点比如6 - 1 - 2 - null并且要删除6那么头节点会发生变化。如果不用 dummy就需要单独处理头节点连续被删除的情况。用了 dummy 后所有节点都可以统一看作删除 cur.next不管删除的是不是原来的头节点逻辑都一致。删除节点时的关键点删除cur.next时应该写cur.nextcur.next.next;此时cur不应该立刻向后移动。因为新的cur.next可能仍然是需要删除的节点。只有当前节点后面的节点不需要删除时才移动curcur.next;经典题型四快慢指针快慢指针是链表题中的高频技巧。它通常使用两个指针slow每次走一步fast每次走两步由于速度不同它们可以用来解决很多问题找链表中点判断链表是否有环找环的入口删除倒数第N个节点判断回文链表这一节先讲最基础的两个找中点和判断环。快慢指针例题一寻找链表中点题目给定单链表头节点head返回链表的中间节点。如果有两个中间节点通常返回第二个中间节点。示例1 - 2 - 3 - 4 - 5 返回 3 1 - 2 - 3 - 4 - 5 - 6 返回 4解题思路使用两个指针slow 每次走一步 fast 每次走两步当fast到达链表末尾时slow正好走到中间位置。Java 代码实现classSolution{publicListNodemiddleNode(ListNodehead){ListNodeslowhead;ListNodefasthead;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;}returnslow;}}为什么偶数长度返回第二个中点以1 - 2 - 3 - 4 - 5 - 6为例。当fast每次走两步到达末尾后slow会停在节点4。所以这个写法返回的是第二个中间节点。如果题目要求返回第一个中间节点可以调整循环条件。但大多数入门题默认返回第二个中点。复杂度分析时间复杂度O(n)空间复杂度O(1)快慢指针例题二判断链表是否有环题目给定一个链表判断链表中是否有环。有环链表示意1 - 2 - 3 - 4 ^ | |_________|解题思路仍然使用快慢指针slow每次走一步fast每次走两步如果链表没有环fast最终会走到null。如果链表有环fast会在环中不断追赶slow。因为fast比slow每轮多走一步所以它们最终一定会相遇。Java 代码实现publicclassSolution{publicbooleanhasCycle(ListNodehead){ListNodeslowhead;ListNodefasthead;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;if(slowfast){returntrue;}}returnfalse;}}为什么要判断fast ! null fast.next ! null因为fast每次要走两步fastfast.next.next;如果fast或fast.next是null就会出现空指针异常。所以循环条件必须保证fast 当前存在 fast 的下一个节点也存在复杂度分析时间复杂度O(n)空间复杂度O(1)当链表题需要判断中点、长度差或是否成环时可以让两个指针以不同速度移动。进阶例题删除链表倒数第 N 个节点题目给定链表头节点head和整数n删除链表倒数第n个节点并返回头节点。示例输入1 - 2 - 3 - 4 - 5, n 2 输出1 - 2 - 3 - 5解题思路这道题也可以用快慢指针。核心是让fast先走n步然后slow和fast一起走。当fast走到链表末尾时slow就在待删除节点的前一个位置。为了方便删除头节点仍然使用 dummy 节点。Java 代码实现classSolution{publicListNoderemoveNthFromEnd(ListNodehead,intn){ListNodedummynewListNode(0);dummy.nexthead;ListNodefastdummy;ListNodeslowdummy;for(inti0;in;i){fastfast.next;}while(fast.next!null){fastfast.next;slowslow.next;}slow.nextslow.next.next;returndummy.next;}}为什么从 dummy 开始如果要删除的是第一个节点例如1 - 2 - 3 n 3删除后头节点应该变成2。使用 dummy 可以统一处理这种情况。slow最终停在待删除节点的前一个节点。如果待删除的是原头节点那么slow正好停在 dummy 上。复杂度分析时间复杂度O(n)空间复杂度O(1)常见坑点链表题最容易错在哪里1. 修改指针前没有保存后续节点反转链表时如果直接写cur.nextprev;curcur.next;这里的cur.next已经被改成了prev原来的下一个节点丢失了。正确写法应该先保存ListNodenextcur.next;cur.nextprev;curnext;2. 返回了错误的头节点反转链表后新的头节点不是原来的head而是prev。合并链表时如果用了 dummy返回的不是dummy而是returndummy.next;删除节点时如果头节点可能变化也应该返回returndummy.next;3. 没有处理空链表和单节点链表很多链表题都需要考虑head null head.next null迭代反转链表可以自然处理这两种情况。但递归写法必须显式判断if(headnull||head.nextnull){returnhead;}4. 快慢指针循环条件写错如果代码中有fastfast.next.next;循环条件通常应该是while(fast!nullfast.next!null)不要只判断while(fast!null)否则fast.next可能为空。5. 删除节点后指针移动错误删除链表中所有等于val的节点时if(cur.next.valval){cur.nextcur.next.next;}else{curcur.next;}删除后不要立刻移动cur。因为新的cur.next可能仍然需要删除。模板总结链表题常用写法链表遍历模板ListNodecurhead;while(cur!null){// 处理 curcurcur.next;}反转链表模板ListNodeprevnull;ListNodecurhead;while(cur!null){ListNodenextcur.next;cur.nextprev;prevcur;curnext;}returnprev;虚拟头节点模板ListNodedummynewListNode(0);dummy.nexthead;ListNodecurdummy;while(cur.next!null){// 根据题目处理 cur.next}returndummy.next;快慢指针模板ListNodeslowhead;ListNodefasthead;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;}总结链表题的难点不在于代码很长而在于指针关系容易写乱。你可以重点记住下面几句话链表节点通过next指针连接修改指针前先保存后续节点反转链表使用prev、cur、next合并链表和删除节点常用 dummy 节点简化边界快慢指针适合找中点、判环、删除倒数节点如果头节点可能变化通常应该考虑虚拟头节点循环条件要和指针移动方式匹配避免空指针异常链表题一开始写慢一点很正常。建议每次写代码前先在纸上画出节点和指针再决定每一步修改哪个next。
第15篇-链表基础-反转链表-合并链表与快慢指针
概述为什么链表题容易让初学者卡住学完栈和队列之后我们继续看另一类非常基础、也非常高频的数据结构链表。数组和链表都可以存储一组元素。但它们最大的区别在于数组依靠下标访问元素 链表依靠指针连接元素这也导致链表题和数组题的思维方式很不一样。数组题常常在想下标 i 怎么移动 区间边界在哪里而链表题常常在想当前节点是谁 下一个节点是谁 指针应该先保存还是先修改很多初学者做链表题时最容易出现的问题不是思路完全不会而是指针断了节点丢了循环条件写错返回了错误的头节点忘记处理空链表或单节点链表这篇文章会围绕链表最常见的四个方向展开链表的基本结构与指针操作反转链表合并两个有序链表快慢指针解决中点、环形链表等问题学完这篇你应该能看懂链表指针变化并能独立写出反转链表、合并链表和快慢指针这几类高频题。核心概念链表到底是什么链表是一种由节点组成的数据结构。每个节点通常包含两部分值当前节点存储的数据指针指向下一个节点的位置单链表可以表示成head | v [1] - [2] - [3] - [4] - null在 Java 中常见的链表节点定义如下publicclassListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.valval;}ListNode(intval,ListNodenext){this.valval;this.nextnext;}}其中val表示节点值next表示下一个节点head表示链表头节点如果head null说明链表为空。链表和数组的区别对比项数组链表内存结构连续存储节点分散存储访问元素可通过下标随机访问只能从头逐个遍历查找第i个元素O(1)O(n)插入删除节点可能需要移动大量元素修改指针即可常见考点下标、区间、双指针指针修改、头节点、快慢指针链表最核心的能力不是快速访问而是通过修改指针关系改变节点之间的连接方式。链表题的本质不是操作值而是操作节点之间的next指针。基础操作遍历链表遍历链表是所有链表题的基础。ListNodecurhead;while(cur!null){System.out.println(cur.val);curcur.next;}这里的cur是一个移动指针。它从头节点开始每次移动到下一个节点。遍历过程cur | v [1] - [2] - [3] - null cur | v [1] - [2] - [3] - null cur | v [1] - [2] - [3] - null当cur null时说明已经走到链表末尾。遍历时常见错误错误写法while(cur.next!null){curcur.next;}这个循环会停在最后一个节点而不是遍历所有节点。如果你需要处理每个节点通常应该写while(cur!null){curcur.next;}当然如果题目明确需要停在最后一个节点前面才会使用cur.next ! null。指针操作为什么要先保存后修改链表题最重要的一条经验是修改next指针前先想清楚后面的节点会不会丢。比如有链表1 - 2 - 3 - null如果当前cur指向节点1cur.nextnull;那么节点2和节点3就无法再通过cur找到了。所以在修改指针前通常要先保存下一个节点ListNodenextcur.next;cur.nextnull;curnext;这也是反转链表中最关键的动作。经典题型一反转链表题目给定单链表头节点head请反转链表并返回反转后的头节点。示例输入1 - 2 - 3 - 4 - 5 - null 输出5 - 4 - 3 - 2 - 1 - null解题思路反转链表的核心是把每个节点的next指针反过来。原链表1 - 2 - 3 - null反转后3 - 2 - 1 - null我们使用三个指针prev当前节点反转后应该指向的前一个节点cur当前正在处理的节点next提前保存cur.next防止链表断开后找不到后续节点初始状态prev null cur head每一轮做三件事1. 保存 next cur.next 2. 反转 cur.next prev 3. 两个指针向后移动prev cur, cur nextJava 代码实现classSolution{publicListNodereverseList(ListNodehead){ListNodeprevnull;ListNodecurhead;while(cur!null){ListNodenextcur.next;cur.nextprev;prevcur;curnext;}returnprev;}}执行过程以1 - 2 - 3 - null为例第一轮next 2 1.next null prev 1 cur 2结果1 - null 2 - 3 - null第二轮next 3 2.next 1 prev 2 cur 3结果2 - 1 - null 3 - null第三轮next null 3.next 2 prev 3 cur null结果3 - 2 - 1 - null最后cur null循环结束prev就是新的头节点。复杂度分析时间复杂度O(n)每个节点处理一次空间复杂度O(1)只使用常数个指针反转链表的关键是先保存next再修改cur.next最后移动prev和cur。反转链表的递归写法反转链表也可以用递归完成。递归思路是先反转后面的链表再把当前节点接到反转结果的末尾。代码如下classSolution{publicListNodereverseList(ListNodehead){if(headnull||head.nextnull){returnhead;}ListNodenewHeadreverseList(head.next);head.next.nexthead;head.nextnull;returnnewHead;}}递归代码怎么理解假设链表是1 - 2 - 3 - null递归调用reverseList(2)会把后半部分反转成3 - 2 - null此时head仍然是节点1并且原来的关系还是1 - 2要把1接到2后面需要head.next.nexthead;也就是2 - 1然后断开原来的指向head.nextnull;否则会形成环1 - 2递归写法更简洁但对初学者来说不如迭代直观。刷题时建议先熟练掌握迭代写法。递归复杂度时间复杂度O(n)空间复杂度O(n)递归调用栈占用空间经典题型二合并两个有序链表题目将两个升序链表合并为一个新的升序链表并返回合并后的头节点。示例输入 1 - 2 - 4 1 - 3 - 4 输出 1 - 1 - 2 - 3 - 4 - 4解题思路这道题和归并排序中的合并过程很像。每次比较两个链表当前节点的值谁小就把谁接到结果链表后面对应链表指针向后移动重复直到其中一个链表为空最后把剩余链表接到结果后面这里常用一个技巧虚拟头节点。什么是虚拟头节点虚拟头节点也叫 dummy 节点。它不是最终答案中的真实节点只是为了简化代码。如果不用 dummy就要单独处理第一个节点结果链表头节点到底应该是 l1 还是 l2用了 dummy 后可以统一写成dummy - 已合并部分最后返回dummy.nextJava 代码实现classSolution{publicListNodemergeTwoLists(ListNodelist1,ListNodelist2){ListNodedummynewListNode(0);ListNodecurdummy;while(list1!nulllist2!null){if(list1.vallist2.val){cur.nextlist1;list1list1.next;}else{cur.nextlist2;list2list2.next;}curcur.next;}if(list1!null){cur.nextlist1;}if(list2!null){cur.nextlist2;}returndummy.next;}}为什么最后可以直接接上剩余链表因为两个输入链表本身已经是升序的。当其中一个链表为空时另一个链表剩下的节点也已经有序。所以不需要继续一个个比较直接接到结果链表末尾即可。复杂度分析时间复杂度O(n m)两个链表每个节点最多访问一次空间复杂度O(1)只使用常数个额外指针其中n和m分别是两个链表的长度。虚拟头节点可以统一处理结果链表的连接逻辑避免单独判断新链表头节点。经典题型三删除链表节点删除节点也是链表题中的基础操作。如果要删除某个值等于val的节点常见写法如下classSolution{publicListNoderemoveElements(ListNodehead,intval){ListNodedummynewListNode(0);dummy.nexthead;ListNodecurdummy;while(cur.next!null){if(cur.next.valval){cur.nextcur.next.next;}else{curcur.next;}}returndummy.next;}}为什么删除节点也适合用 dummy如果要删除的是头节点比如6 - 1 - 2 - null并且要删除6那么头节点会发生变化。如果不用 dummy就需要单独处理头节点连续被删除的情况。用了 dummy 后所有节点都可以统一看作删除 cur.next不管删除的是不是原来的头节点逻辑都一致。删除节点时的关键点删除cur.next时应该写cur.nextcur.next.next;此时cur不应该立刻向后移动。因为新的cur.next可能仍然是需要删除的节点。只有当前节点后面的节点不需要删除时才移动curcur.next;经典题型四快慢指针快慢指针是链表题中的高频技巧。它通常使用两个指针slow每次走一步fast每次走两步由于速度不同它们可以用来解决很多问题找链表中点判断链表是否有环找环的入口删除倒数第N个节点判断回文链表这一节先讲最基础的两个找中点和判断环。快慢指针例题一寻找链表中点题目给定单链表头节点head返回链表的中间节点。如果有两个中间节点通常返回第二个中间节点。示例1 - 2 - 3 - 4 - 5 返回 3 1 - 2 - 3 - 4 - 5 - 6 返回 4解题思路使用两个指针slow 每次走一步 fast 每次走两步当fast到达链表末尾时slow正好走到中间位置。Java 代码实现classSolution{publicListNodemiddleNode(ListNodehead){ListNodeslowhead;ListNodefasthead;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;}returnslow;}}为什么偶数长度返回第二个中点以1 - 2 - 3 - 4 - 5 - 6为例。当fast每次走两步到达末尾后slow会停在节点4。所以这个写法返回的是第二个中间节点。如果题目要求返回第一个中间节点可以调整循环条件。但大多数入门题默认返回第二个中点。复杂度分析时间复杂度O(n)空间复杂度O(1)快慢指针例题二判断链表是否有环题目给定一个链表判断链表中是否有环。有环链表示意1 - 2 - 3 - 4 ^ | |_________|解题思路仍然使用快慢指针slow每次走一步fast每次走两步如果链表没有环fast最终会走到null。如果链表有环fast会在环中不断追赶slow。因为fast比slow每轮多走一步所以它们最终一定会相遇。Java 代码实现publicclassSolution{publicbooleanhasCycle(ListNodehead){ListNodeslowhead;ListNodefasthead;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;if(slowfast){returntrue;}}returnfalse;}}为什么要判断fast ! null fast.next ! null因为fast每次要走两步fastfast.next.next;如果fast或fast.next是null就会出现空指针异常。所以循环条件必须保证fast 当前存在 fast 的下一个节点也存在复杂度分析时间复杂度O(n)空间复杂度O(1)当链表题需要判断中点、长度差或是否成环时可以让两个指针以不同速度移动。进阶例题删除链表倒数第 N 个节点题目给定链表头节点head和整数n删除链表倒数第n个节点并返回头节点。示例输入1 - 2 - 3 - 4 - 5, n 2 输出1 - 2 - 3 - 5解题思路这道题也可以用快慢指针。核心是让fast先走n步然后slow和fast一起走。当fast走到链表末尾时slow就在待删除节点的前一个位置。为了方便删除头节点仍然使用 dummy 节点。Java 代码实现classSolution{publicListNoderemoveNthFromEnd(ListNodehead,intn){ListNodedummynewListNode(0);dummy.nexthead;ListNodefastdummy;ListNodeslowdummy;for(inti0;in;i){fastfast.next;}while(fast.next!null){fastfast.next;slowslow.next;}slow.nextslow.next.next;returndummy.next;}}为什么从 dummy 开始如果要删除的是第一个节点例如1 - 2 - 3 n 3删除后头节点应该变成2。使用 dummy 可以统一处理这种情况。slow最终停在待删除节点的前一个节点。如果待删除的是原头节点那么slow正好停在 dummy 上。复杂度分析时间复杂度O(n)空间复杂度O(1)常见坑点链表题最容易错在哪里1. 修改指针前没有保存后续节点反转链表时如果直接写cur.nextprev;curcur.next;这里的cur.next已经被改成了prev原来的下一个节点丢失了。正确写法应该先保存ListNodenextcur.next;cur.nextprev;curnext;2. 返回了错误的头节点反转链表后新的头节点不是原来的head而是prev。合并链表时如果用了 dummy返回的不是dummy而是returndummy.next;删除节点时如果头节点可能变化也应该返回returndummy.next;3. 没有处理空链表和单节点链表很多链表题都需要考虑head null head.next null迭代反转链表可以自然处理这两种情况。但递归写法必须显式判断if(headnull||head.nextnull){returnhead;}4. 快慢指针循环条件写错如果代码中有fastfast.next.next;循环条件通常应该是while(fast!nullfast.next!null)不要只判断while(fast!null)否则fast.next可能为空。5. 删除节点后指针移动错误删除链表中所有等于val的节点时if(cur.next.valval){cur.nextcur.next.next;}else{curcur.next;}删除后不要立刻移动cur。因为新的cur.next可能仍然需要删除。模板总结链表题常用写法链表遍历模板ListNodecurhead;while(cur!null){// 处理 curcurcur.next;}反转链表模板ListNodeprevnull;ListNodecurhead;while(cur!null){ListNodenextcur.next;cur.nextprev;prevcur;curnext;}returnprev;虚拟头节点模板ListNodedummynewListNode(0);dummy.nexthead;ListNodecurdummy;while(cur.next!null){// 根据题目处理 cur.next}returndummy.next;快慢指针模板ListNodeslowhead;ListNodefasthead;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;}总结链表题的难点不在于代码很长而在于指针关系容易写乱。你可以重点记住下面几句话链表节点通过next指针连接修改指针前先保存后续节点反转链表使用prev、cur、next合并链表和删除节点常用 dummy 节点简化边界快慢指针适合找中点、判环、删除倒数节点如果头节点可能变化通常应该考虑虚拟头节点循环条件要和指针移动方式匹配避免空指针异常链表题一开始写慢一点很正常。建议每次写代码前先在纸上画出节点和指针再决定每一步修改哪个next。
