1. 如何判断一个链表是否带环
2. 如何找到链表中的环的第一个节点

第一个问题很好找，就是设置两个指针,p , q 。 其中 p每次向前移一个，q每次向前移两个，如果q能追的上p，则链表带环，时间复杂度为O(n), 空间复杂度为O(1)
第二个问题是室友在面某投行IT部门时的题目（可惜啊，俺过不了该投行的电话面试）。这个题目最容易的做法就是用一个数组记录遍历过的节点，然后第一次遍历到已经访问过的节点时就可以了。据室友说，题目要求空间复杂度为O(1) . 因此显然不能用这个方法了。
我想了一下，一开始想了一个O(n*n)的方法，后来受那个求两个链表第一个公共节点的题目的启发，想到了一个O(n)的算法，
大概就是这样：找到环中的任意一个节点，这个很容易找，在判断链表是否包含环的步骤中，当p,q 相遇时，p和q必定在环内，不妨取p，再设r为p的下一个节点,在p和r之间将环打断，这时可以得到两个链表  h...p, r...p, (h为链表头结点), 然后再将链表 h..p逆转(此时r..p必然变为 r...h)，求得链表p...h与r..h的第一个公共子节点就是所求的点。最后将p..h逆转回来，将p和r连接上，即可得到原链表。空间复杂度为O(1), 时间复杂度为O(n).