check list cycle

检查链表是否有环，是个常见的面试题，面试官太没创意了。

常见的答案是，用两个指针，同时遍历链表，一个一次挪动一个位置，一个一次挪动两个位置，如果有环，两个必然有相等的时候，这个类似两个速度不一样的人跑圈，快的总会追上慢的。

这个题目的额外要求往往是，不能用额外的存储空间，不然hash做记录，记下遍历过的元素就行了。其实指针是个很好的额外空间，指针总是4或8的倍数，低2位或低4位可以用来存储额外的信息。

在判断链表是否有环时，可以用next指针做”额外“存储，每次遍历，检查 next & 0x01，如果true，说明这个节点遍历过，否则 next |= 0x01，标记已经来过。这样当然破坏了链表，不过可以在所有检查完成后，做一个恢复。

还有一种解法，将链表倒序，如果有环，一定能回到表头。

通常发现环后，需要找到环的起点，用指针法最简单，第一次碰到 next & 0x01 的地方就是环的起点。另外两种方法，需要预估链表的长度（快的指针经历的步数，或回到表头需要的步数），然后遍历链表，依次假设节点是环的起点，如果超过最大遍历次数，没回到，说明下一个可能是环的起点。