Leetcode 142 Linked List Cycle I

著名的跳跃链表题目。忽然想记这个的题解是因为早上忽然想起这个题，一时竟想不起来找入口的解法。

随手上网翻出来的答案都是在找到相遇点之后，一个点从头开始，一个点从相遇点开始，轮次进行步长都为1的移动，可证相遇点必为环的起始点。

总记得自己的方法不一样，到公司翻了一下之前写的代码发现果然不同。

思路：

设我们用两个点，点A 点B， 若要其相遇，可以使点B先行环长L步。然后A点从初始点，B点从L步之后，都开始进行步长为1的移动，则其相遇点必为入口。

证明：

当点A第一次到达入口时，点B则在入口往前L步处，因环长为L，则AB此时恰好相遇。

代码：

/**  
 * 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 NULL;
        }
        ListNode *p1 = head;
        ListNode *p2 = head;
        int counter1 = 0;
        int counter2 = 0;
        int meet = 0;
        int cycleLength = 0;
        int nocycleLength = 0;
        while (true){
            int tmp = 0;
            p1 = p1 -> next;
            if (p1 == NULL){
                return NULL;
            }
            p2 = p2 -> next;
            if (p2 == NULL){
                return NULL;
            }
            p2 = p2 -> next;
            if (p2 == NULL){
                return NULL;
            }
            counter1 += 1;
            counter2 += 2;
            if (p1 == p2 && meet == 0){ //meet for the first time
                tmp = counter1;
                meet = 1;
            }else if (p1 == p2 && meet == 1){ //meet for the second time
                cycleLength = counter1 - tmp;
                nocycleLength = tmp / cycleLength;
                break;
            }

        }
        p1 = head;
        for (int i = 0; i < cycleLength; i++){
            head = head -> next;
        }
        while (true){
            if (p1 == head){
                return head;
            }
            p1 = p1->next;
            head = head->next;
        }
        return NULL;
    }

};