<数据结构/算法> leetcode hot100系列. 141(142). 环形链表

[LeetCode hot 100] 141(142). 环形链表

题目链接

环形链表的判断在要求空间复杂度为O(1)时，需要使用Floyd判圈法来判断是否存在环。Floyd判圈法的具体讲解看这里。

具体步骤为：

1. 快指针fast和慢指针slow指向链表头（首元结点）
2. fast每次移动两步，slow每次移动一步
3. 如果遇到null说明没有环，如果fast和slow相遇说明有环，进入4
4. 其中一个指针移回链表头，另一个不动
5. 两个指针每次移动一步，直到相遇，就是环的入口

完整代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next && fast->next->next){
            fast = fast->next->next;
            slow = slow->next;
            if(slow == fast){
                fast = head;
                while(fast != slow){
                    fast = fast->next;
                    slow = slow->next;
                }
                return fast;
            }
        }
        return nullptr;
    }
};