佛山外贸网站建设价位,第一站长网,wordpress调用文章方法,搜狐焦点石家庄房产网问题入口
思想#xff1a;Floyds Tortoise and Hare
这个算法简单来说就是设置一个慢指针#xff08;一次移动一个位置#xff09;和一个快指针#xff08;一次移动两个位置#xff09;。在遍历过程中#xff0c;如果慢指针和快指针都指向同一个元素#xff0c;证明环…问题入口
思想Floyds Tortoise and Hare
这个算法简单来说就是设置一个慢指针一次移动一个位置和一个快指针一次移动两个位置。在遍历过程中如果慢指针和快指针都指向同一个元素证明环存在否则环不存在。
点击上面这个标题链接主要是帮助我们理解为什么这两个指针一定会相遇ps. 即使两个指针起点位置不同依然成立。
s为慢指针f为快指针。假设他们之间的距离为10如下图所示。 经历一次移动s会向前走一步此时距离会变成10111。f向前走两步此时距离会变成9。 综上快慢指针的距离会一次次减少最终相遇。
class Solution {
public:ListNode *slow, *fast;bool hasCycle(ListNode *head) {slow head;fast head;while(fast ! NULL fast-next ! NULL){fast fast-next-next;slow slow-next;if (fast slow) return true;}return false;}
};
注意fast ! NULL fast - next ! NULL。
