【单链表算法实战】解锁数据结构核心谜题—

【单链表算法实战】解锁数据结构核心谜题——环形链表

题目如下：

在这里插入图片描述

解题过程如下：

环形链表：尾结点的next指针不为空，而是指向链表中的任一结点。
在这里插入图片描述
思路：快慢指针，慢指针每次走一步，快指针每次走两步。快慢指针在环中追逐相遇，那么这个链表为环形链表；快慢指针没有相遇，那么这个链表不是环形链表。

在这里插入图片描述

完整代码如下：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {//快慢指针，相遇为环形链表，否则不是环形链表ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast){return true;}}return false;
}

试着证明：

在环形链表中，快慢指针，慢指针每次走1步，快指针每次走2步，在环中追逐一定会相遇。

具体示例画图分析，slow和fast之间的距离变化：1 2 3 2 1 0，3是这里的最大距离。但是，在面试中被问到如何求证，可不能画一个具体例子说明，这就不是证明了！
在这里插入图片描述

slow和fast入环之后，分析追逐的过程中距离的变化，既然一定会存在最大距离，那么假设此时slow刚入环，slow和fast的最大距离为N，之后每追击1次，距离会缩小1步：
在这里插入图片描述

最终slow和fast的距离为0，说明一定会相遇。

在环形链表中，快慢指针，慢指针每次走1步，快指针每次走3/4/5……步，在环中追逐一定会相遇吗？

在环形链表中，慢指针每次走1步，快指针每次走3步，假设此时slow刚入环，slow和fast的最大距离为N，之后每追击1次，距离会缩小2步，在环中追逐的过程中距离的变化：

N为奇数时，下一圈会相遇吗？N为奇数时，下一圈追逐：
当C - 1为偶数时，即C为奇数，一定会相遇；
当C - 1为奇数时，即C为偶数，一定不会相遇。

在这里插入图片描述

上图为例，慢指针每次走1步，快指针每次走3步，快慢指针走过的路程之间的关系：3 * 慢指针 = 快指针

假设：入环结点到头结点的距离是L，此时slow刚刚入环，fast已经在环内绕了n圈。

快慢指针走的路程分别为：
慢指针：L
快指针：L + C - N + nC

根据公式3 * 慢指针 = 快指针：2L = (n + 1)C - N
先分析2L：由于偶数 * 偶数 = 偶数；偶数 * 奇数 = 偶数，所以2L一定是偶数。
已知N为奇数，由于偶数 = 偶数 - 偶数；偶数 = 奇数 - 奇数，所以(n + 1)C一定是奇数，若当中C为偶数，那么(n + 1)C也为偶数，与结论(n + 1)C一定是奇数相悖，所以C一定是奇数。

由于：

N为奇数时，下一圈会相遇吗？N为奇数时，下一圈追逐：
当C - 1为偶数时，即C为奇数，一定会相遇；
当C - 1为奇数时，即C为偶数，一定不会相遇。

综上，在环形链表中，慢指针每次走1步，快指针每次走3步，快慢指针在环中追逐一定会相遇。同理，慢指针每次走1步，快指针每次走4/5/……步，快慢指针在环中追逐也一定会相遇，证明过程同上。

慢指针每次走1步，快指针每次走3步，完整代码如下：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {//快慢指针，慢指针每次走1步，快指针每次走3步ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){slow = slow->next;int n = 3;while (n--){if (fast->next){fast = fast->next;}else{return false;}}if (slow == fast){return true;}}return false;
}