Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Note: Do not modify the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0 Output: tail connects to node index 0 Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1 Output: no cycle Explanation: There is no cycle in the linked list.
第一步：
1. 设置一个慢指针，一次走一步
2. 设置一个快指针，一次走两步
3. 如果慢指针和快指针都指向同一个地址，则表明为这是一个环。
4. 否则，无环
第二步：
1. L1：头结点和入口结点之间的距离
2. L2：入口结点和相遇结点之间的距离
3. C：环的长度
4. n：快指针绕环一周的次数（当第一次，快慢指针相遇）
===> 1. 当相遇，慢指针经过的总距离：L1+L2
===> 2. 当相遇，快指针经过的总距离：L1+L2 + n*C
===> 头部位置和入口位置之间的距离=相遇位置（fast）和入口位置（entry）向前移动之间的距离。
class Solution { public: ListNode *detectCycle(ListNode *head) { if (head == NULL || head->next == NULL) return NULL; ListNode *slow = head; ListNode *fast = head; bool isCycle = false; while (slow != NULL && fast != NULL) { slow = slow->next; if (fast->next == NULL) return NULL; fast = fast->next->next; if (slow == fast) { isCycle = true; break; } } if (!isCycle) return NULL; slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; } };
LeetCode 142. Linked List Cycle II
原文：https://www.cnblogs.com/douzujun/p/10657735.html