题目：
141.Given a linked list, determine if it has a cycle in it.
142.Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
思路：
带环链表如图所示。设置一个快指针和一个慢指针，快指针一次走两步，慢指针一次走一步。快指针先进入环，慢指针后进入环。在进入环后，可以理解为快指针追赶慢指针，由于两个指针速度相差1，则最终会相遇。
当快指针和慢指针相遇时，证明链表中存在环。141可解。
假设两个指针在C点相遇，此时慢指针走过的路程为AB+BC，快指针走过的路程为AB+BC+CB+BC。由于时间相同，快指针的速度为慢指针的2倍，则快指针走过的路程为慢指针的2倍。因此，2*（AB+BC）=AB+BC+CB+BC，得到AB=CB。
由此可以得到两个结论：
- 环的长度即为AB+BC，即A到C的长度。
- 当快指针和慢指针相遇后，把快指针放置于A点（即链表头部），慢指针仍在C点。此时两个指针一次走一步，相遇的节点即为环的起点。142可解。
代码：
141. Linked List Cycle
struct ListNode {
int val;
ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *fast = head;
ListNode *slow = head;
while ((fast != NULL) && (slow != NULL) && (fast->next != NULL)) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
return true;
}
}
return false;
}
};
142. Linked List Cycle II
struct ListNode {
int val;
ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *fast = head;
ListNode *slow = head;
while ((fast != NULL) && (slow != NULL) && (fast->next != NULL)) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
fast = head;
while (fast != slow) {
fast = fast->next;
slow = slow->next;
}
return fast;
}
}
return NULL;
}
};