力扣笔记：判断链表是否成环以及返回入环的第一个节点

从评论区看到的一个思路：
1.首先快指针一定比慢指针多走n圈以上(n>=1)
2.在慢指针走完第一圈之前，快指针一定会追上慢指针

相遇的时候，慢指针走过的节点是：x+y；快指针走过的节点是x+n(y+z)+y;
所以，2(x+y)=x+n(y+z)+y; x=z+(n-1)(y+z)
也就是说：分别从头节点和相遇节点处出发的两个节点（temp1、temp2），每次移动一个节点，一定会在入环节点处相遇。且移动的节点数：temp1是：x，temp2是：z+(n-1)(y+z)

顺便总结一下是否成环的判断方法：

1. 链表为空 或 链表只有一个节点，且next指向本身，此时一定不存在环；
2. 存在环的话，fast每次移动两个节点，slow每次移动一个节点，一旦fast或fast 的next为NULL，说明链表不存在环；一旦fast==slow,就说明环存在；

/** * 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) {
   
        //x+y=x+n*(y+z)+y
        //先判断是否有环，如果有环，那么相遇点和起点处的两个指针同时移动，每次移动一个节点，一定能够在入环节点处相遇；
        ListNode* fast=head,*slow=head;
        while(fast!=NULL&&fast->next!=NULL){
   
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow){
   //相遇
            ListNode* temp1=fast;
            ListNode* temp2=head;
            while(temp1!=temp2){
   
                temp1=temp1->next;
                temp2=temp2->next;
            }
            return temp1;
            }
        }
        return nullptr;
        
    }
};