LeetCode 142. Linked List Cycle II

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.

解析：
这个题目是在LeetCode 141. Linked List Cycle 进行的提升，如果存在环，则返回环的入口位置。
以此图为例介绍。

假设环入口距离链表头的长度为L，快慢指针相遇的位置为cross，且该位置距离环入口的长度为S。考虑快慢指针移动的距离，慢指针走了L+S，快指针走了L+S+nR(这是假设相遇之前快指针已经绕环n圈)。由于快指针的速度是慢指针的两倍，相同时间下快指针走过的路程就是慢指针的两倍，所以有2(L+S)=L+S+nR，化简得L+S=nR
当n=1时，即快指针在相遇之前多走了一圈，即L+S=R，也就是L=R−S，观察图片，L表示从链表头到环入口的距离，而R−S表示从cross继续移动到环入口的距离，既然二者是相等的，那么如果采用两个指针，一个从表头出发，一个从cross出发，那么它们将同时到达环入口。即二者相等时便是环入口节点

当n>1时，上式为L=nR−S，L仍然表示从链表头到达环入口的距离，而nR−S可以看成从cross出发移动nR步后再倒退S步，从cross移动nR步后回到cross位置，倒退S步后是环入口，所以也是同时到达环入口。即二者相等时便是环入口节点

所以寻找环入口的方法就是采用两个指针，一个从表头出发，一个从相遇点出发，一次都只移动一步，当二者相等时便是环入口的位置
代码如下：

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
    public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL)
            return head;
        ListNode *fast = head;
        ListNode *slow = head;
        bool cycle_flag = false;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if(fast == slow) {
                cycle_flag = true;
                break;
            }
        }
        if(!cycle_flag)
            return NULL;
        ListNode *temp = head;
        while(temp->next && slow->next && temp != slow) {
            temp = temp->next;
            slow = slow->next;
        }
        return temp;
    }
}
;

参考：https://blog.csdn.net/sinat_35261315/article/details/79205157