算法模式：快慢指针
在上一篇文章 算法模式：双指针 介绍了双指针模式。本篇文章，再介绍一个即可以用在数组，又可以用在链表中的算法模式：快慢指针。快慢指针，其实是双指针模式的一个变种。所以，两者在很多地方有相通之处。
快慢指针
快慢指针模式，有一个非常出名的名字，叫龟兔赛跑。大家肯定都知道龟兔赛跑啦。但还是再解释一下快慢指针：这种算法的两个指针的在数组上（或是链表上，序列上）的移动速度不一样。还别说，这种方法在解决有环的链表和数组时特别有用。
通过控制指针不同的移动速度（比如在环形链表上），这种算法证明了他们肯定会相遇的。快的一个指针肯定会追上慢的一个（可以想象成跑道上面跑得快的人套圈跑得慢的人）。
咋知道需要用快慢指针模式勒？
问题需要处理环上的问题，比如环形链表和环形数组
当你需要知道链表的长度或是某个特别位置的信息的时候
那啥时候用快慢指针而不是上面的双指针呢？
有些情形下，咱们不应该用双指针，比如我们在单链表上不能往回移动的时候。一个典型的需要用到快慢指针的模式的是当你需要去判断一个链表是否是回文的时候。
LeetCode 141. 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
提示：
链表中节点的数目范围是
[0, 104]-105<= Node.val <= 105pos为-1或者链表中的一个 有效索引 。
进阶：你能用 \$O(1)\$（即，常量）内存解决此问题吗？
思路分析
这道题就是典型的快慢指针的模式：使用两个指针，一个每次走一步，一个每次走两步，如果快指针追上慢指针，则有环；否则，无环。代码如下：
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-03-06 21:23:36
*/
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}202. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19 输出：true 解释： 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1
示例 2：
输入：n = 2 输出：false
提示：
1 <= n <= 231-1
思路分析
这道题也可以用快慢指针来解决。其思路，来个图就一目了然了：
如果不是快乐数，那么变化过程就是一个环。利用快慢指针判断是否有环即可得到答案。
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-10 21:40
*/
public boolean isHappy(int n) {
int slow = n, fast = n;
do {
slow = squareSum(slow);
fast = squareSum(fast);
fast = squareSum(fast);
if (fast == 1) {
return true;
}
} while (slow != fast);
return false;
}
private int squareSum(int num) {
int sum = 0;
while (num > 0) {
int n = num % 10;
sum += n * n;
num /= 10;
}
return sum;
}
// end::answer[]
