优选算法--快乐数（快慢指针）循环链表
文章目录
- 1.快乐数---快慢指针的应用
- 2.环形链表142（师兄版）
1.快乐数—快慢指针的应用
题目描述：
- 1）给定一个数字，计算这个数字每一个数位上面的这个数的平方和，不断的计算下去，直到这个数子的平方和是1，那么这个数字就是快乐数；
- 2）如果最后陷入循环，那么这个平方和就不会是1，就是上面的两个情况；
- 3）我们使用快慢指针解决这个题目，主要是这个无限循环是类似于我们之前学习的这个循环链表的这个解法，因此我们把这个无限循环就理解为这个链表的循环；
- 4）我们定义一个函数，这个函数就是求解一个数字的每一个数位上面的数的平方和；
- 5）在我们的这个主函数里面，我们让这个慢指针指向第一个数字，快指针和慢指针的这个指向不可以是一样的，否则就无法进行下面的这个循环的过程；
- 6）因此我们让这个快指针指向第二个数据，让后快指针走两步，慢指针走一步，看看这个最后的结果会不会是1；用这个返回值决定我们的这个数字是不是快乐数；
代码示例：
2.环形链表142（师兄版）
这个因为上面的题目是用到了这个环形链表的这个思想的，因此在这个地方，我重新把之前写的那道环形链表的题目重新回顾了一下；
| 1） | 判断这个链表里面是不是存在这个环，如果是的话，需要返回这个环的入口节点，否则返回null; |
|---|---|
| 2) | 我们首先需要判断这个链表里面是不是存在这个环，然后去确定这个环里面的这个入口节点； |
| 3） | 如何判断这个链表里面是不是存在这个环，我们使用的就是这个快慢指针的方法： |
| 让这个慢指针一次走一步，快指针一次走两步，他们一定会进入这个环，而且一定会在某一个换里面的节点的位置相遇； | |
| 相遇就说明这个链表里面是存在这个环的；进而去判断这个入口节点； | |
| 4） | 入口节点的判断： |
| 首先定义这个1指向我们的这个相遇的地方（使用指针进行标记） | |
| 然后定义一个指针b指向我们的这个链表的头结点； | |
| 接着就是两个指针同时移动，一次移动一步，相遇的位置就是我们的这个环的入口节点； | |
| 5） | 为什么这个a,b同时开始走，这个相遇的地方就是我们的这个环的入口节点呢？ |
| 其实这个问题是涉及到我们的这个数学的严谨推导的，但是这个结论确实是正确的，感兴趣的可以自行这个数学推理的这个过程（其实就是我们利用这个慢指针的这个路程==快指针的路程/2进行列等式； | |
| 6） | 下面的这个就是我们进行这个数学推理的这个图示，右边就是这个对应的等式的计算过程，我们的这个x表示的就是头结点到这个入口节点的这个路程，n(y+z)就是我们的这个快指针在这个环里面不断的转圈圈形成的这个循环，最后回到了这个相遇节点，这个时候减去y就是我们的这个相遇节点的位置； |
 |
代码解读：
| 1） | 首先就是判断这个链表里面是不是存在这个环嘛； |
|---|---|
| 2） | 我们定义的这个slow和fast都是开始的时候指向这个链表里面的这个头结点的； |
| 3） | 进入我们的这个循环之后，就是我们的这个慢指针一次走一步，快指针一次走两步，直到两个相遇，这个时候就证明我们的这个链表里面是存在这个环的； |
| 4） | 在存在这个环的基础上面，我们使用这个a指向我们的这个相遇的地方，b指向我们的这个链表的头结点，这个时候两个指针一次走一步，相遇的时候就是我们的这个链表里面的这个环的入口节点； |
| 5） | 因为相遇的时候我们的这个ab指向的这个位置是一样的，因此这个时候我们返回a,b任意一个都是可以的，这个就是我们的这个链表里面的这个环的入口节点； |
时候我们返回a,b任意一个都是可以的，这个就是我们的这个链表里面的这个环的入口节点； |
