Hot100代码随想录：相交链表、反转链表与回文链表

Java HOT100 刷题笔记相交链表、反转链表与回文链表学习日期09 月 21 日关键词链表、双指针、链表反转、空间复杂度、节点身份比较本文记录三道经典链表题。重点不是只记住代码而是理解三个可以反复复用的模型路径对齐、指针反转、快慢指针寻找中点。一、相交链表题目链接LeetCode 160. 相交链表1. 题意与关键点给定两个单链表的头节点判断它们是否相交如果相交返回第一个公共节点否则返回null。这里的“相交”比较的是节点对象是否相同而不是节点值是否相同nodeAnodeB下面两个节点即使值相同也不代表相交链表A1 → 8 → 9 链表B2 → 8 → 9只有当两个链表后半部分引用的是同一批节点对象时才算相交Aa1 → a2 ┐ ├→ c1 → c2 Bb1 → b2 ┘2. 方法一数组逆向比较先把两个链表中的节点引用分别保存到数组中再从数组尾部向前比较。链表相交后公共部分必然一直延伸到尾部因此最后一个连续相同区域的起点就是交点。publicclassSolution{publicListNodegetIntersectionNode(ListNodeheadA,ListNodeheadB){intm0;intn0;for(ListNodepheadA;p!null;pp.next){m;}for(ListNodepheadB;p!null;pp.next){n;}ListNode[]nodesAnewListNode[m];ListNode[]nodesBnewListNode[n];ListNodepheadA;for(inti0;im;i){nodesA[i]p;pp.next;}pheadB;for(inti0;in;i){nodesB[i]p;pp.next;}ListNodeintersectionnull;for(intim-1,jn-1;i0j0nodesA[i]nodesB[j];i--,j--){intersectionnodesA[i];}returnintersection;}}复杂度时间复杂度O(m n)空间复杂度O(m n)。这个方法容易理解但额外保存了全部节点没有充分利用链表结构。3. 方法二双指针路径对齐分别设置两个指针pA先走链表A再走链表B pB先走链表B再走链表A两条路线的总长度相等A B B A如果存在交点两个指针会在交点相遇如果不存在交点两个指针最终会同时到达null。publicclassSolution{publicListNodegetIntersectionNode(ListNodeheadA,ListNodeheadB){ListNodepAheadA;ListNodepBheadB;while(pA!pB){pA(pAnull)?headB:pA.next;pB(pBnull)?headA:pB.next;}returnpA;}}复杂度时间复杂度O(m n)空间复杂度O(1)。4. 为什么必须经过null再切换链表不能在“最后一个节点”处直接跳到另一条链表的头部否则无交点时两个指针会一直在两条链表组成的循环路线中移动却没有共同的节点可以作为退出条件。经过null的意义是null是两个无交点链表共有的结束状态有交点时两个指针在交点相遇无交点时两个指针最终同时成为null循环也能结束。因此null不是为了“方便找最后一个节点”而是为了保证算法在无交点时也能正确终止。5. 本题总结双指针法本质上是在消除两个链表长度差较长链表多走的部分 通过交换路线自动抵消只要看到“两个链表长度不同但需要比较后半段位置”就可以考虑路径对齐思想。二、反转链表题目链接LeetCode 206. 反转链表1. 核心思路原链表1 → 2 → 3 → null反转后null ← 1 ← 2 ← 3每次处理当前节点cur时需要完成三件事保存下一个节点避免链表断开后丢失让当前节点指向前一个节点同时向后移动pre和cur。2. 迭代实现classSolution{publicListNodereverseList(ListNodehead){ListNodeprenull;ListNodecurhead;while(cur!null){ListNodenextcur.next;// 1. 保存后继节点cur.nextpre;// 2. 反转当前指针precur;// 3. pre向后移动curnext;// 4. cur向后移动}returnpre;}}指针变化示例初始prenullcur1 第一次null ← 1 2 → 3 → null 第二次null ← 1 ← 2 3 → null 第三次null ← 1 ← 2 ← 3复杂度时间复杂度O(n)空间复杂度O(1)。3. 易错点最容易漏掉的是ListNodenextcur.next;如果直接执行cur.nextpre;却没有提前保存原来的cur.next就会丢失尚未处理的后半部分链表。三、回文链表题目链接LeetCode 234. 回文链表回文结构从左向右和从右向左读取相同例如1 → 2 → 2 → 1 1 → 2 → 3 → 2 → 11. 方法一转成数组后双指针比较链表不能直接从尾部向前访问因此可以先把节点值保存进数组再使用左右双指针。classSolution{publicbooleanisPalindrome(ListNodehead){ListIntegervaluesnewArrayList();for(ListNodecurhead;cur!null;curcur.next){values.add(cur.val);}intleft0;intrightvalues.size()-1;while(leftright){if(!values.get(left).equals(values.get(right))){returnfalse;}left;right--;}returntrue;}}复杂度时间复杂度O(n)空间复杂度O(n)。这个方法直观适合第一次解决问题但没有达到进阶要求的常量空间。2. 方法二快慢指针 反转后半部分步骤使用快慢指针找到前半部分的末尾反转后半部分链表从两端向中间比较可选再次反转后半部分恢复原链表结构。classSolution{publicbooleanisPalindrome(ListNodehead){if(headnull||head.nextnull){returntrue;}ListNodefirstHalfEndfindFirstHalfEnd(head);ListNodesecondHalfStartreverse(firstHalfEnd.next);booleanresulttrue;ListNodelefthead;ListNoderightsecondHalfStart;while(right!null){if(left.val!right.val){resultfalse;break;}leftleft.next;rightright.next;}// 恢复链表避免函数调用后改变输入结构firstHalfEnd.nextreverse(secondHalfStart);returnresult;}privateListNodefindFirstHalfEnd(ListNodehead){ListNodeslowhead;ListNodefasthead;while(fast.next!nullfast.next.next!null){slowslow.next;fastfast.next.next;}returnslow;}privateListNodereverse(ListNodehead){ListNodeprenull;ListNodecurhead;while(cur!null){ListNodenextcur.next;cur.nextpre;precur;curnext;}returnpre;}}复杂度时间复杂度O(n)空间复杂度O(1)。3. 奇数和偶数长度如何处理使用条件while(fast.next!nullfast.next.next!null)循环结束后slow停在前半部分的最后一个节点偶数1 → 2 → 2 → 1 ↑ slow 奇数1 → 2 → 3 → 2 → 1 ↑ slow反转slow.next开始的后半部分后只需要按照后半部分长度进行比较。奇数链表的中间节点不影响回文判断。四、三道题的共同模式题目核心技巧时间复杂度空间复杂度相交链表双指针路径对齐O(mn)O(1)反转链表pre-cur-next三指针O(n)O(1)回文链表快慢指针 反转后半段O(n)O(1)可以提炼出以下链表解题习惯改变next前先保存原来的后继节点比较是否为同一节点时使用不要只比较val需要找中点时优先考虑快慢指针需要从后往前比较时可以考虑反转链表修改输入链表后实际开发中应考虑是否需要恢复原结构。五、复盘这三道题分别训练了链表中最常见的三种能力路径长度不同 → 双指针换路对齐 链表方向改变 → pre、cur、next 前后对称比较 → 找中点并反转后半部分真正需要记住的不是某一段完整代码而是每个指针在当前时刻代表什么以及修改指针后是否还能够找到剩余链表。