給定一個單鏈表
1. 如何判斷鏈表是否存在環(huán)?
2. 如何知道環(huán)的長度?
3. 如何找出環(huán)的連接點在哪里?
4. 帶環(huán)鏈表的長度?
解法:
1. 對于問題1
使用追趕的方法,設定兩個指針show,fast,從頭節(jié)點開始,每次分別前進1步,2步,如存在環(huán)則兩者必然會相遇,如不存在環(huán),則fast遇到null退出,并且碰撞點到頭節(jié)點的距離為環(huán)中節(jié)點數n.
2. 對于問題2:
記錄下問題1的碰撞點p,碰撞點p肯定是在環(huán)中的,從這個節(jié)點觸發(fā),一邊移動一邊計數再次回到這個節(jié)點就得到了環(huán)中節(jié)點數n
3. 對于問題3:
有定理: 碰撞點p到連接點的距離=頭節(jié)點到連接點的距離,因此分別從碰撞點,頭節(jié)點相同速度開始走相遇的那個點就是連接點.
定理證明如下:
設頭節(jié)點到連接點的距離為x,連接點到碰撞點的距離為y,碰撞點到連接點的距離為z,環(huán)的長度為n,
(1) 碰撞點到頭節(jié)點的距離為n,則有x+y=n
(2) 又因為環(huán)的長度為n,則有y+z=n
(3) 由(1),(2) 可得,碰撞點p到連接點的距離=頭節(jié)點到連接點的距離
4. 對于問題4
問題3中已經求出連接點距離頭指針的長度,加上問題2中求出的環(huán)的長度,二者之和就是帶環(huán)鏈表的長度.
