LeetCode链表经典五题：从相交到环形，双指针的妙用

你好我是fengxin_rou这是我的个人主页fengxin_rou的主页❄️欢迎查看我的专栏我的专栏《Java后端学习》、《JAVASE基础》、《JUC并发》、《redis》、《JVM虚拟机》、《MYSQL》、《黑马点评》、《rabbitmq》、《JavaWebAI的talis学习系统》、《苍穹外卖》目录引言一、相交链表双指针的巧妙应用1.1 题目描述1.2 核心思路1.3 代码实现1.4 详细解析1.5 复杂度分析1.6 边界情况二、反转链表迭代法详解2.1 题目描述2.2 核心思路2.3 代码实现2.4 详细解析2.5 图解演示2.6 复杂度分析三、回文链表快慢指针与反转结合3.1 题目描述3.2 核心思路3.3 代码实现3.4 详细解析3.5 边界情况四、环形链表快慢指针检测4.1 题目描述4.2 核心思路4.3 代码实现4.4 详细解析4.5 数学证明4.6 复杂度分析五、环形链表II数学推导的精妙5.1 题目描述5.2 核心思路5.3 代码实现5.4 数学推导5.5 为什么这个推导成立5.6 复杂度分析六、总结与最佳实践6.1 技术总结6.2 最佳实践6.3 常见陷阱七、常见问题解答Q1: 为什么双指针法能解决相交问题Q2: 反转链表时为什么要保存下一个节点Q3: 快慢指针找中点时奇偶长度有什么区别Q4: 环形链表II的数学推导为什么成立Q5: 这些技巧在实际开发中有什么应用摘要本文深入剖析LeetCode链表专题的五道经典题目从相交链表到环形链表II全面讲解双指针技术的应用。通过详细的代码分析、图解演示和数学推导帮助读者掌握链表操作的核心技巧。引言链表作为数据结构中的基础结构是算法面试中的高频考点。LeetCode上的链表题目不仅考察对指针操作的理解更考验逻辑思维和问题抽象能力。本文精选五道经典链表题目涵盖相交、反转、回文、环检测等核心问题通过双指针技术这一强大工具带你深入理解链表操作的精髓。一、相交链表双指针的巧妙应用1.1 题目描述给定两个单链表的头节点headA和headB找出并返回两个单链表相交的起始节点。如果不存在相交节点返回null。C1 - C2 - C3, List B: B1 - B2 - B3 - C1 - C2 - C3. Show two pointers starting at headA and headB, moving forward, and meeting at the intersection node C1. Professional engineering style with clear labels. 尺寸1024x768 风格自然 质量高质量 --1.2 核心思路双指针法让两个指针分别从两个链表的头节点开始遍历当一个指针到达链表末尾时跳转到另一个链表的头节点继续遍历。如果两个链表相交两个指针必然会在交点相遇。1.3 代码实现public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode A headA, B headB; while(A ! B){ A A ! null ? A.next : headB; B B ! null ? B.next : headA; } return A; } }1.4 详细解析指针移动规则指针A从headA开始遍历到达末尾后跳转到headB指针B从headB开始遍历到达末尾后跳转到headA当A B时要么是交点要么都是null无交点为什么这个方法有效设链表A的长度为a公共部分长度为c链表B的长度为b公共部分长度为c则指针A走过的路径a c b跳转后走B的非公共部分 指针B走过的路径b c a跳转后走A的非公共部分两者相等因此必然会在交点相遇。1.5 复杂度分析时间复杂度O(m n)其中m和n分别是两个链表的长度空间复杂度O(1)只使用了两个指针1.6 边界情况两个链表都为空一个链表为空另一个不为空两个链表没有交点两个链表长度相同且有交点二、反转链表迭代法详解2.1 题目描述给定单链表的头节点head请你反转链表并返回反转后的链表。2 - 3 - 4 - 5. Intermediate steps showing pointer changes with pre, cur, tmp pointers. Final reversed list: 5 - 4 - 3 - 2 - 1. Use arrows to show pointer movements. Professional technical illustration style. 尺寸1024x768 风格自然 质量高质量 --2.2 核心思路迭代法使用三个指针逐步调整每个节点的next指针方向。2.3 代码实现class Solution { public ListNode reverseList(ListNode head) { ListNode pre null; ListNode cur head; while( cur ! null){ ListNode tmp cur.next; // 存储下一个节点 cur.next pre; // 反转当前节点 pre cur; // pre前进一步 cur tmp; // cur前进一步 } return pre; // pre是新的头节点 } }2.4 详细解析指针角色pre前一个节点初始为nullcur当前节点初始为headtmp临时存储下一个节点防止链表断裂操作步骤保存cur.next到tmp将cur.next指向pre反转pre移动到curcur移动到tmp2.5 图解演示以链表1 - 2 - 3 - 4 - 5为例步骤precurtmp操作初始null1--1null121.next null21232.next 132343.next 243454.next 3545null5.next 4结束5null-返回52.6 复杂度分析时间复杂度O(n)遍历一次链表空间复杂度O(1)只使用了常数个指针三、回文链表快慢指针与反转结合3.1 题目描述给定一个单链表的头节点head请你判断该链表是否为回文链表。如果是返回true否则返回false。3.2 核心思路三步法使用快慢指针找到链表中点反转后半部分链表比较前半部分和反转后的后半部分3.3 代码实现class Solution { public boolean isPalindrome(ListNode head) { ListNode mid middleNode(head); ListNode head2 reverseList(mid); while(head2 ! null){ if(head.val ! head2.val){ return false; } head head.next; head2 head2.next; } return true; } private 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; } private ListNode reverseList(ListNode head){ ListNode cur head; ListNode pre null; while( cur ! null){ ListNode tmp cur.next; cur.next pre; pre cur; cur tmp; } return pre; } }3.4 详细解析快慢指针找中点slow每次移动一步fast每次移动两步当fast到达末尾时slow刚好在中点为什么这样能找到中点奇数长度链表slow停在正中间偶数长度链表slow停在中间偏右的位置3.5 边界情况链表为空链表只有一个节点链表长度为偶数链表长度为奇数四、环形链表快慢指针检测4.1 题目描述给你一个链表的头节点head判断链表中是否有环。如果链表中存在环则返回true否则返回false。0 - -4 - back to 2. Show slow and fast pointers moving, meeting inside the cycle. Professional engineering style with clear labels. 尺寸1024x768 风格自然 质量高质量 --4.2 核心思路快慢指针法快指针每次移动两步慢指针每次移动一步。如果存在环快指针最终会追上慢指针。4.3 代码实现public class Solution { 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.4 详细解析为什么快指针一定能追上慢指针如果存在环快指针和慢指针都会进入环中快指针速度是慢指针的两倍相对速度为1因此快指针每轮都会接近慢指针一个节点的距离最终必然会在环内某点相遇4.5 数学证明设环的长度为L快指针和慢指针的初始距离为D每轮快指针比慢指针多走1步则相遇所需轮数D轮4.6 复杂度分析时间复杂度O(n)最坏情况下需要遍历整个链表空间复杂度O(1)只使用了两个指针五、环形链表II数学推导的精妙5.1 题目描述给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。5.2 核心思路两步法使用快慢指针找到环内相遇点从相遇点和头节点同时出发每次一步最终在环入口相遇5.3 代码实现public class Solution { public ListNode detectCycle(ListNode head) { ListNode slow head, fast head; while(true){ if(fast null || fast.next null) return null; slow slow.next; fast fast.next.next; if(slow fast) break; } fast head; while(slow ! fast){ slow slow.next; fast fast.next; } return fast; } }5.4 数学推导变量定义a头节点到环入口的距离b环入口到相遇点的距离c相遇点到环入口的距离环剩余部分环的总长度b c第一次相遇时慢指针走过的距离a b快指针走过的距离a b n(b c)n是快指针绕环的圈数速度关系 快指针速度是慢指针的两倍因此2(a b) a b n(b c)化简得a (n-1)(b c) c结论 从相遇点和头节点同时出发每次一步经过a步后必然在环入口相遇。5.5 为什么这个推导成立慢指针进入环时快指针已经在环内某处快指针每次比慢指针多走一步最终会追上慢指针相遇时快指针比慢指针多走了整数圈5.6 复杂度分析时间复杂度O(n)需要遍历链表空间复杂度O(1)只使用了两个指针六、总结与最佳实践6.1 技术总结题目核心技术时间复杂度空间复杂度相交链表双指针O(mn)O(1)反转链表迭代法O(n)O(1)回文链表快慢指针反转O(n)O(1)环形链表快慢指针O(n)O(1)环形链表II快慢指针数学推导O(n)O(1)6.2 最佳实践指针操作要细心每次移动指针前先保存下一个节点边界条件要覆盖空链表、单节点、偶数长度等情况复杂度要分析时间复杂度和空间复杂度都要考虑图解辅助理解画图是理解指针操作的最佳方式代码要简洁避免冗余变量保持代码清晰6.3 常见陷阱空指针异常访问next前检查节点是否为null无限循环确保循环条件正确链表断裂反转时要保存下一个节点边界遗漏测试所有可能的边界情况七、常见问题解答Q1: 为什么双指针法能解决相交问题A: 因为两个指针走过的总路径长度相同。如果两个链表相交指针必然会在交点相遇如果不相交指针会同时到达两个链表的末尾都为null。Q2: 反转链表时为什么要保存下一个节点A: 因为反转当前节点的next指针后就会丢失对下一个节点的引用。保存tmp cur.next可以防止链表断裂。Q3: 快慢指针找中点时奇偶长度有什么区别A:奇数长度slow停在正中间偶数长度slow停在中间偏右的位置两种情况都能正确处理回文判断Q4: 环形链表II的数学推导为什么成立A: 这基于速度差原理。快指针速度是慢指针的两倍因此快指针会比慢指针多走整数圈。通过数学推导可以证明从相遇点和头节点同时出发必然在环入口相遇。Q5: 这些技巧在实际开发中有什么应用A:链表相交数据库连接池、多级缓存架构链表反转撤销操作、历史记录回文检测字符串处理、数据校验环检测死锁检测、循环依赖分析