【图文解析】给定一个链表，判断链表中是否有环

例题描述

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例一：

• 输入：head = [3,2,0,-4], pos = 1
• 输出：true
• 解释：链表中有一个环，其尾部连接到第二个结点。
  

示例二：

• 输入：head = [1,2], pos = 0
• 输出：true
• 解释：链表中有一个环，其尾部连接到第一个节点。
  

示例三：

• 输入：head = [1], pos = -1
• 输出：false
• 解释：链表中没有环。
  

结点结构体定义

struct ListNode {
	int val;
	struct ListNode *next;
};

解题思路

快慢指针遍历链表，快指针步距为2，慢指针步距为1，如果链表带环，两指针一定会在环中相遇。

1. 判断极端条件，如果链表为空，或者链表只有一个结点，一定不会带环，直接返回NULL。
2. 创建快慢指针，都初始化指向头结点。因为快指针每次都要步进2个单位，所以在判断其自身有效性的同时还要判断其next指针的有效性，在循环条件中将两语句逻辑与并列起来。
   
3. 单次循环中，如果快指针与慢指针相等，即指向的相同的地址（同一结点），则说明有环，返回true。否则到达链表结尾跳出循环后返回false。
   
   
   【此时快慢指针指向了同一个结点，说明这个链表中有环】

为什么快指针步距为2，慢指针步距为1，如果有环就一定会相遇呢？
这是一个数学问题，因为能被2整除的数，一定会被1整除，所以二者一定会相遇 ~
我们可以猜想一下如果快指针步距为3，慢指针步距为1，还肯定会相遇吗？其实不然，用数学的角度来看，他们也许永不相遇：
【比如环有2个结点，此时快慢指针位于不同结点上，这样无论循环多少次，他们永不会相遇】：
无数次擦肩而过，却永远都在错过，世间最远的距离，不过如此。我愿稍顿步足，等待与你的邂逅，可怎奈轮回(while循环)戏人，伊人如斯，不胜叹惋，唯缦立远视矣。。。我哭了，你呢T_T

代码实现

bool hasCycle(ListNode *head) {
	if(head == NULL || head->next == NULL){
		return false;
	}
	struct ListNode *slow = head;
	struct ListNode *fast = head;
	while(fast != NULL && fast->next != NULL){
		fast = fast->next->next;
		slow = slow->next;
        if(fast == slow){
            return true;
        }
    }
    return false;
}