142.环形链表II

https://leetcode.cn/problems/linked-list-cycle-ii/

方法1:使用容器的方法

我们遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环,且该节点就是入环节点

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode*> s;
        //遍历链表
        while(head)
        {
            //判断该节点是否曾经出现过
            if(s.count(head))
            {
                return head;
            }
            s.insert(head);
            head = head->next;
        }
        return NULL;
    }
};

方法2:快慢指针

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        //先判断链表是否有环
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)    
            {
               //说明有环
               //一个指针从该位置走,一个指针从头开始走,二者一次走一步,当二者再次相遇,此时就是入环节点
               ListNode* meet = slow;
               fast = head;
               while(meet != fast)
               {
                   meet = meet->next;
                   fast = fast->next;
               }
               return meet;
            }
        }
        return NULL;
    }
};

附加问题:求环的长度

我们可以得知: 距离A == 距离C 入环节点到相遇点的距离为B
则:fast指针从链表头一步一步走向fast指针的距离（A+C）=== 环的长度（B+C）

所以我们的思路就是:

• 第一步：先找到相遇的节点（方法：判断链表中是否有环,快慢指针）
• 第二步：让其中一个指针从头开始走,一次走一步,用count计数，当它与相遇节点相遇时,此时的count就是环的长度

注意点:不能直接: fast = head count = 0 因为有可能环链表只有一个节点,此时meet == fast == slow, 如果按这个思路,最后返回的count就是0,err

正确思路:因为至少有一个节点,所以fast指针初始化为头节点的下一个位置,count置为1

class Solution {
public:
    int detectCycle(ListNode *head) {
        //先判断链表是否有环
        ListNode* fast = head;
        ListNode* slow = head;
        int count = 0;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)    
            {
               //说明有环
               //一个指针从该位置走,一个指针从头开始走,二者一次走一步,当二者再次相遇,此时就是入环节点
               ListNode* meet = slow;
               fast = head->next;//初始化为头的下一个节点！！！
               count = 1;//至少一个节点！！！
               while(fast != meet) //
               {
                   count++;// 计数++
                   fast = fast->next;
               }
               return count;
            }
        }
        return -1;
    }
};