【牛客题霸题解】链表中环的入口节点

前置题目：NC4判断链表中是否有环
在判断链表是否有环那道题目中，我们的做法是定义两个指针初始指向头结点，然后快指针每次走两步，慢指针每次走一步。如果快慢指针相遇的话，就表示链表中有环。
然后我们观察一下，这个相遇的结点有没有什么用途

如图所示，我们设链表头结点到环入口结点的距离是 （如果知道了这个距离其实就可以知道环入口结点时哪一个了）
环入口结点到快慢指针相遇的结点的距离为
快慢指针相遇结点到环入口结点的距离为
一开始相遇的时候，是慢指针走了（慢指针走完一圈之前必相遇，这个事情在NC4里证明过了）
快指针走了
也可以说是快指针走了 为正整数且。
所以
我们的目的是为了求a，所以我们化简一下式子

这样就说明，从相遇结点开始走，走a步的话会走到环入口结点（因为b+c等于转了一圈）
那我们先找到相遇结点，然后一个指针从链表头结点开始走，一个指针从相遇结点开始走，当两个指针相遇的时候，就是环入口结点了。
c++

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(slow != NULL && fast->next != NULL && fast->next->next!=NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)
            {
                slow = head;
                while(slow != fast)
                {
                    fast = fast->next;
                    slow = slow->next;
                }
                return slow;
            }
        }
        return NULL;
    }
};

java

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(slow != null && fast.next != null && fast.next.next!=null)
        {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow)
            {
                slow = head;
                while(slow != fast)
                {
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
}

python

class Solution:
    def detectCycle(self , head ):
        fast = head
        slow = head
        while slow is not None and fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                slow = head
                while slow != fast:
                    fast = fast.next
                    slow = slow.next
                return slow
        return None