题目
解释
主要使用两个快慢指针,定义一个快指针和一个慢指针,慢指针一次走一步、快指针一次走两步。如下图所示,要是两者相遇,则证明有环。
代码如下
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle(ListNode *head) { //创建两个快慢指针,要求慢指针一次走一步。快指针一次走两步 //刚开始快慢指针都是从头节点开始遍历的 ListNode * fast = head; ListNode * slow = head; //下面进入循环,也就是一直遍历,不满足就返回false while(slow != nullptr && fast->next != nullptr && fast->next->next != nullptr) { slow = slow->next; //慢指针向前遍历一位 fast = fast->next->next; //快指针向前遍历两位 if(slow == fast ) //如果两者相遇,则证明有环 { return true; } } return false;//否则无环 } };