背景：昨晚跟前同事们宵夜被问道判断单向链表有无环的算法，第一次接触到快慢指针，觉得有意思！
旧思路：通过内存缓存路线，比对路线判断是否有环。
- 优点（时间复杂度低）：一遍算完
- 缺点（空间复杂度高）：内存占用与链表长度成正比
新思路：通过设定两个角色（快慢指针）分别以单节点与2倍（注意：任何大于或等于2倍数都行）单节点速度依次遍历，当出现两角色同时访问一个节点则表示存在环。
- 优点1 （空间复杂度低）：只占用两个角色的内存
- 优点2（时间复杂度低）：一遍算完
发散问题：怎么找到形成环的节点？
假设：第一个相遇步骤数N，第二次相遇步骤数M
- 计算环的大小
M-N - 计算指定范围查找形成环的节点
从 N-（M-N）= 2N - M 开始查找 - 利用快慢指针查找环节点
快慢指针都从 2N - M 开始，保持间距 M-N，按顺序遍历节点。当快慢节点第一次相同时则为形成换的节点
网友评论