程序原题

Given a linked list, determine if it has a cycle in it. 

题目翻译

给定一个链表，判断其中是否含有环。

题目分析

这是一道经典的不能再经典的面试题……

请看过这道题目的同学们先不要脱口而出答案。我们来假设我们是第一次看到这个题，应该从哪儿着手呢？

一个最最自然的想法是——记住哪些节点出现过，哪些没有。重复出现了节点就说明了链表中有环。我们可以：1）在每个走过的节点留下一些“印记”，这样会弄脏输入数据；2）我们用一个Set来记录每一个走过节点的内存地址，这其实在我看来是一个很自然很好的解法，唯一的缺点是需要用O(n)的额外空间。

这道题的“标准解答”是——“快慢指针技巧”。slow指针和fast指针开始同时指向头结点head，fast每次走两步，slow每次走一步。如果链表不存在环，那么fast或者fast.next会先到None。如果链表中存在环路，则由于fast指针移动的速度是slow指针移动速度的两倍，所以在进入环路以后，两个指针迟早会相遇，如果在某一时刻slow==fast，说明链表存在环路。

遗憾的是，如果我是面试官，在候选人说出这个答案的时候我会判定这个候选人肯定看过这个标准解答……从而我会把面试重点换成编程风格和写程序是否熟练……并且会在心里默默准备下一道题目……

但是如果候选人能够分析出如上几种可能的解答再给出最优解答，那一定是会大大加分的！

程序实现