leetcode141 环形链表

leetcode141 环形链表

 

time O(n)space O(1)

快慢指针法：

使用fast指针以两步步长更新，使用slow以一步步长更新；

tips：

while判断的条件通过短路表达式 fast && fast->next 如果fast为NULL 那么就不会访问 fast->next，循环不执行；如果fast->next为NULL 那么循环也不会执行，所以不会访问fast->next->next;只有当fast->next不为NULL时，fast->next->next才至少能访问NULL才有意义，所以有效避免了指针的越界；

/**
 * 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,*slow=head;
        while(fast && fast->next){
            slow=slow->next;
            fast=fast->next->next;
            if(fast==slow) return true;
        }
        return false;
    }
};