给一个链表，如果里面有环，输出环的起点，否则输出空指针
这是最容易想到的解法，因为一个节点的地址可以唯一确定这个节点，只要沿着链表移动，看节点对应的地址是否出现过就行了，unordered_set比set查找快一点，所以可以用unordered_set。代码如下：
/** * 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) { unordered_set<ListNode*> mp; while(head) { if(mp.count(head) != 0) return head; mp.insert(head); head = head->next; } return nullptr; } };解法一时间效率还可以，但是需要O(n)的空间，不符合题目要求，所以需要新的方法。
链表判环可以使用快慢指针的方法，慢指针每次走一步，快指针每次走两步，如果链表中有环，那么快慢指针一定会相遇。
但是快慢指针的相遇点可能是环的任意位置，而本题需要找到环的入口点，那么应该怎么办呢？
实际上这里有一个简单的数学关系，设head为头节点，entry为入口点，meet为相遇点，head到entry的距离是L1，entry到meet的距离为L2，meet再到entry的距离为L3，也就是说整个环的长度为L2+L3。那么对于快慢指针相遇的情况，慢指针走的距离为L1+L2，快指针走的距离为L1+L2+n(L3+L2)，因为快慢指针能相遇的话，快指针一定比慢指针多走了n圈，而快指针走的总距离是慢指针的两倍，所以L1+L2=n(L3+L2)，由此可以得到L1=(n-1)(L2+L3)+L3，即L1的长度为L3加上固定圈数的环的长度。所以如果快慢指针相遇以后，meet和head一起移动，他俩相遇的地方就是entry点。
想想这个道理：meet可能会在环里转很多圈，但不论转多少圈，都会回到它开始的位置，所以meet和head一起走，一定会在entry处相遇。
代码如下：
/** * 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) return nullptr; ListNode *slow = head, *fast = head, *entry = head; while(fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) { while(slow != entry) { slow = slow->next; entry = entry->next; } return entry; } } return nullptr; } };
