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).