快慢指针法深度解析：解决链表环、中点、倒数第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 进阶应用：回文链表判断

结合反转链表技巧：

1. 找到中点
2. 反转后半部分
3. 比较前后两部分

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 True

4. 倒数第K个节点的快慢指针解法

传统解法需要两次遍历，快慢指针可实现一次遍历：

1. 快指针先走K步
2. 两指针同步移动直至快指针到达末尾

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超过链表长度时返回头节点
• K=0时返回null
• 空链表直接返回null

5. 性能对比与工程实践

三种问题的性能对比：

实际编码中的常见陷阱：

1. 快指针移动时需要先检查fast.next是否为空
2. 处理偶数长度链表时中点的选择（左或右）
3. 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

这个案例完美展示了快慢指针在中点查找中的关键作用，以及如何与其他链表操作组合解决复杂问题。