附上原题：
给定一个链表，如果该链表存在环路，要求返回环路的开始节点，否则返回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没有白刷。
