[leetcode Linked List Cycle II]

附上原题：

给定一个链表，如果该链表存在环路，要求返回环路的开始节点，否则返回NULL。第一个版本只要求判断链表是否存在环路，而这道题在这基础上又增加了难度。

记得上初中的时候，学校开运动会，其中有一项是三千米跑步，这对运动员们的耐力是巨大的考验。经常会出现这样一种情况，跑的快的同学从后面又追上了跑得慢的同学，也就是说，跑的快的那位同学比慢的那位整整快了一圈。

不知道大家有没有从这个故事当中收到启发，操作本身就是一个环路，才使得快得同学可以重新追上慢的同学，如果操场是直线，那根本就不可能追上。重新回到我们的问题上，要判断链表是否存在环路，我是不是可以定义两个指针，第一个指针每次走1歩，第二个指针每次走两步，如果第二个指针与第一个指针又重新相遇，那我们认为存在环路；否则当第二个指针最终指向了NULL，则不存在。这是第一问的解，仔细思考应该不难。

我们来直接观察下面这幅图：

链表的总长度为8，环路的长度为5。我们先让指针P2向前走了5歩，也就是链表的长度，然后P1还是指向第一个节点。我们发现当P2跟P1同时往前再走3歩，它们相遇的节点刚好是环路的开始节点，这难道是巧合？我们来分析下，假设链表的长度为k，环路的长度为d，那么剩余的节点长度为k-d。当P2从头节点向前走了k歩以后，此时它距离最后一个节点的位置还有k-d-1歩，如果它再走一步，就达到了环路的起始位置。再来看P1，P1距离环路的开始节点刚好相差k-d歩，证毕。

那现在的问题是如何获得环路的长度呢？这个其实不难，运用两个指针，第一个指针每次走两步，第二个指针每次走一步，等到他们相遇后，记录他们相遇的节点。然后继续往前，直到再次到达相遇节点，此时走过的路程就为环路的长度。分析完成后，我们用代码将它实现。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        int cycleLen = caculateCycleDistance(head);
        if (cycleLen == 0) {
            return NULL;
        }
        ListNode *first = head;
        ListNode *second = head;
       //第一个指针向前走的步数等于环路的长度
        while (cycleLen != 0) {
            second = second->next;
            cycleLen--;
        }
        //两个指针同时向前，相遇后的节点即为环路的开始节点
        while (first != second) {
            first = first->next;
            second = second->next;
        }
        return first;
    }

   /**
    * 计算环路的长度，若不存在环路，返回0
    */
    int caculateCycleDistance(ListNode *head) {
        int cycleLen = 0;

        ListNode *first = head;
        if (!first) {
            return cycleLen;
        }
        ListNode *second = head->next;
        //一个指针每次走一步，另一个指针每次走两步
        //注意每次移动指针的过程中，都要判断是否为NULL
        while (first && second && first != second) {
            first = first->next;
            second = second->next;
            if (!second)
                return cycleLen;
            second = second->next;
        }
        if (first && second) {
            ListNode *meetNode = first; //记录两个指针相遇的节点
            do {
                first = first->next;
                cycleLen++;
            } while (first != meetNode);
        }
        return cycleLen;
    }
};

算法一旦分析完成后，实现起来并不难。唯一需要注意的是，每次移动指针的时候，记得判断指针是否为空。写这段程序的时候，写完第一次提交竟然就直接Accepted了，出乎我的意料。看来这段时间的leetcode没有白刷。