【牛客题霸题解】判断链表中是否有环

没有环的链表尾节点会指向空

有环的链表会有一个节点指向链表中以存在的节点

链表如果没有环的话，我们顺着链表的节点一直走下去，一定会遇到空节点。但是如果有环的话，我们一直顺着链表的节点走下去，就会造成死循环，
那我们如何判断链表中是否有环呢？
设置两个指针，一个指针一次走一步，另一个指针一次走两步,如果两个指针相遇的话，那这个链表就是有环的，这个解法时间复杂度,额外空间复杂度。表示链表中节点个数

下面来证明一下为什么有环的话两个指针一定会相遇，以及一定可以在n次操作之内相遇
当慢指针进入环的入口节点的时候，快指针一定在环内的某个位置，假设快慢指针这时的距离为t。如下图快指针和慢指针之间的距离就是8

然后每一次快指针走两步，慢指针走一步，所以进行一次操作以后，快慢指针之间的距离是t-1，再操作一次是t-2、t-3...直到操作t次以后，快慢指针之间的距离为0，即两个指针相遇，所以，如果链表有环的话，快慢指针一定可以在n次操作以内相遇
c++

class Solution {
public:
    bool hasCycle(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)
            {
                return true;
            }
        }
        return false;
    }
};

java

public class Solution {
    public boolean hasCycle(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)
            {
                return true;
            }
        }
        return false;
    }
}

python

class Solution:
    def hasCycle(self , head ):
        fast = head
        slow = head
        while slow!=None and fast.next!=None and fast.next.next!=None:
            fast = fast.next.next;
            slow = slow.next;
            if fast==slow:
                return True
        return False