1. 如何判斷一個(gè)鏈表是否帶環(huán)
2. 如何找到鏈表中的環(huán)的第一個(gè)節(jié)點(diǎn)

第一個(gè)問題很好找，就是設(shè)置兩個(gè)指針,p , q 。 其中 p每次向前移一個(gè)，q每次向前移兩個(gè)，如果q能追的上p，則鏈表帶環(huán)，時(shí)間復(fù)雜度為O(n), 空間復(fù)雜度為O(1)
第二個(gè)問題是室友在面某投行IT部門時(shí)的題目（可惜啊，俺過不了該投行的電話面試）。這個(gè)題目最容易的做法就是用一個(gè)數(shù)組記錄遍歷過的節(jié)點(diǎn)，然后第一次遍歷到已經(jīng)訪問過的節(jié)點(diǎn)時(shí)就可以了。據(jù)室友說，題目要求空間復(fù)雜度為O(1) . 因此顯然不能用這個(gè)方法了。
我想了一下，一開始想了一個(gè)O(n*n)的方法，后來受那個(gè)求兩個(gè)鏈表第一個(gè)公共節(jié)點(diǎn)的題目的啟發(fā)，想到了一個(gè)O(n)的算法，
大概就是這樣：找到環(huán)中的任意一個(gè)節(jié)點(diǎn)，這個(gè)很容易找，在判斷鏈表是否包含環(huán)的步驟中，當(dāng)p,q 相遇時(shí)，p和q必定在環(huán)內(nèi)，不妨取p，再設(shè)r為p的下一個(gè)節(jié)點(diǎn),在p和r之間將環(huán)打斷，這時(shí)可以得到兩個(gè)鏈表? h...p, r...p, (h為鏈表頭結(jié)點(diǎn)), 然后再將鏈表 h..p逆轉(zhuǎn)(此時(shí)r..p必然變?yōu)?r...h)，求得鏈表p...h與r..h的第一個(gè)公共子節(jié)點(diǎn)就是所求的點(diǎn)。最后將p..h逆轉(zhuǎn)回來，將p和r連接上，即可得到原鏈表?？臻g復(fù)雜度為O(1), 時(shí)間復(fù)雜度為O(n).