快慢指针法深度解析：解决链表环、中点、倒数第K节点3类问题的统一思路

快慢指针法深度解析解决链表环、中点、倒数第K节点3类问题的统一思路链表操作是算法面试中的高频考点而快慢指针法则是解决链表问题的利器。本文将深入剖析快慢指针的核心思想展示如何用这一技巧优雅解决链表环检测、寻找中点、定位倒数第K节点这三类经典问题。1. 快慢指针法的基本原理快慢指针Fast-Slow Pointers是一种通过两个指针以不同速度遍历链表来解决问题的技巧。其核心在于快指针每次移动两步fast fast-next-next慢指针每次移动一步slow slow-next这种速度差会产生以下关键特性当快指针到达链表末尾时慢指针正好位于链表中间位置。这个特性是解决多种链表问题的基础。快慢指针的通用代码模板如下ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; // 根据具体问题在此添加判断逻辑 }2. 链表环检测与入口定位2.1 环检测原理当链表存在环时快指针最终会追上慢指针类似于环形跑道上的运动员def hasCycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False数学证明设环外长度为L环长为C。当慢指针进入环时快指针已在环中移动L步距离慢指针C-L%c。由于每步距离差1经过C-L%c次移动后两指针必然相遇。2.2 环入口定位算法找到相遇点后将其中一个指针移回头部两指针同速移动再次相遇点即为环入口public ListNode detectCycle(ListNode head) { ListNode slow head, fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { fast head; while (slow ! fast) { slow slow.next; fast fast.next; } return slow; } } return null; }3. 链表中点查找的变体与应用3.1 基础中点查找快指针到达末尾时慢指针即为中点链表长度中点位置奇数正中间偶数靠右节点ListNode* middleNode(ListNode* head) { ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; } return slow; }3.2 进阶应用回文链表判断结合反转链表技巧找到中点反转后半部分比较前后两部分def isPalindrome(head): # 找中点 slow fast head while fast and fast.next: slow slow.next fast fast.next.next # 反转后半部分 prev None while slow: tmp slow.next slow.next prev prev slow slow tmp # 比较 left, right head, prev while right: if left.val ! right.val: return False left left.next right right.next return True4. 倒数第K个节点的快慢指针解法传统解法需要两次遍历快慢指针可实现一次遍历快指针先走K步两指针同步移动直至快指针到达末尾public ListNode getKthFromEnd(ListNode head, int k) { ListNode fast head, slow head; while (k-- 0) { fast fast.next; } while (fast ! null) { slow slow.next; fast fast.next; } return slow; }边界条件处理K超过链表长度时返回头节点K0时返回null空链表直接返回null5. 性能对比与工程实践三种问题的性能对比问题类型时间复杂度空间复杂度快慢指针适用性环检测O(n)O(1)★★★★★中点查找O(n)O(1)★★★★★倒数第K节点O(n)O(1)★★★★☆实际编码中的常见陷阱快指针移动时需要先检查fast.next是否为空处理偶数长度链表时中点的选择左或右K值校验避免越界访问// 安全的快指针移动写法 while (fast fast-next) { // 双重检查 fast fast-next-next; // 移动两步 // ... }6. 综合应用案例链表重排序结合中点查找和反转操作实现L0→Ln→L1→Ln-1...的重排序def reorderList(head): if not head or not head.next: return # 找中点 slow fast head while fast.next and fast.next.next: slow slow.next fast fast.next.next # 反转后半部分 prev, curr None, slow.next slow.next None while curr: tmp curr.next curr.next prev prev curr curr tmp # 合并 first, second head, prev while second: tmp1, tmp2 first.next, second.next first.next second second.next tmp1 first, second tmp1, tmp2这个案例完美展示了快慢指针在中点查找中的关键作用以及如何与其他链表操作组合解决复杂问题。