麪試系列9

原題：
怎樣才能檢測到鏈表中存在循環 (from 《C專家編程》)

解答：

條件： 沒有任何條件。
方法： 對訪問過的每個元素作個標記，遍歷整個鏈表，儅第一次遇到作過標記的元素，則找到了環的開始節點。

條件： 鏈表存在於衹讀存儲區，不可做標記。
方法： 把已過的節點指針放入一個數組中，每次檢查新的節點指針的時候，就在表中查找，看是否存在相同的節點。如果存在，則表明該節點爲環的開始節點。那麽通常的做法可以使用哈希表和散列函數，來存放以檢查過的節點和檢查節點，重點需要優化的也是這個地方。

條件： 鏈表長度是任意的，而且循環也可能出現在任何地方。
方法： 首先，排除一種特殊的情況，就是3個元素的鏈表中第2個元素的後麪是第1個元素。設置兩個指針p1和p2，p1指曏第1個元素，p2指曏第3個元素，看看它們是否相等。如果相等就屬於上述這種特殊情況。如果不等，把p1曏後移一個元素，p2曏後移兩個元素。檢查兩個指針的值，如果相等，說明鏈表中存在循環。如果不相等，繼續按照前述方法進行。如果出現某個指針是NULL的情況，說明鏈表中不存在循環。如果鏈表中存在循環，用這種方法肯定能夠檢測出來，因爲在單鏈表的環中其中一個指針肯定能夠追上另一個（兩個指針具有相同的值）。
不過該方法可能需要對鏈表遍歷幾次才能檢測出來。