引言
單鏈表的尾環(huán)問題是一個比較經(jīng)典的問題初厚，它涉及的問題如下:
1>給一個單鏈表茸时，判斷其中是否有環(huán)的存在;
2>如果存在環(huán)，找出環(huán)的入口點;
3>如果存在環(huán)椎眯，求出環(huán)上節(jié)點的個數(shù);
4>如果存在環(huán)神帅，求出鏈表的長度;
5>如果存在環(huán)再姑，求出環(huán)上距離任意一個節(jié)點最遠的點(對面節(jié)點)；
6>(擴展)如何判斷兩個無環(huán)鏈表是否相交
7>(擴展）如果相交找御，求出第一個相交的節(jié)點.
下面在分析帶環(huán)鏈表的特征的基礎上來一一解決這些問題.
尾環(huán)鏈表特征分析
1.下圖是尾環(huán)鏈表的結構询刹。我們采用快慢指針的方法，很明顯的萎坷，這是一個典型的“跑道追及問題”,倆指針進入“跑道”，速度不一樣沐兰，那么倆指針必然會在某一時刻相遇哆档。
因此判斷鏈表是否有環(huán)的關鍵就是判斷倆指針是否能相遇:
/**
* 判斷是否有回環(huán)
*
* @return
*/
public boolean isLoop() {
if (isEmpty()) {
return false;
}
SNode<T> slow = headNode;
SNode<T> fast = headNode;
while (slow != null && fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {//倆哥們相遇，則返回true
return true;
}
}
//如果是單鏈表住闯，快指針肯定會走到結尾跳出循環(huán)
return false;
}
2.下面分析入口點問題瓜浸。如下圖:
說明：a為頭到入口的距離,x為入口到相遇點的距離,r為環(huán)長度,鏈表長度為L，設定環(huán)的位置以入口為原點比原，順時針為正方向插佛。這里為了更加清晰的說理，這里特殊到一般分兩種情況分析:
1>環(huán)較大量窘，倆指針在環(huán)內一周之內相遇:當slow到達入口時雇寇，fast走了2a,在環(huán)內的位置為2a-a = a,此時fast在環(huán)上順時針領先slow距離為a，相應的slow在環(huán)上順時針"領先"fast的距離為r-a,因為每一步fast都比slow快一步蚌铜，所以再經(jīng)過r-a步锨侯，fast就可以追上slow了，此時相遇時冬殃，slow共走了a+(r-a)=r步囚痴，那么在環(huán)的位置為r-a,此時有相遇點到入口的順時針距離正好為a，與頭結點到入口的距離相等;
2>環(huán)較小审葬，快指針已經(jīng)在環(huán)里浪了n(n>=1)圈才與慢指針相遇:設頭結點到相遇點的距離為s,那么fast走了2s,另外fast在環(huán)里轉了n圈距離為(nr + s),所以有2s = s+nr得s = nr;又有a+x=s=nr,得a + x = (n-1)r + (L - a),推出a = (n-1)*r+(L-a-x);后者為環(huán)上相遇點到入口的順時針距離.前者代表環(huán)轉圈路程深滚，這個公式表示的現(xiàn)實意義為:設定倆指針，一個指針p從head出發(fā)向入口運動,另外一個指針q從相遇點出發(fā)在環(huán)內順時針運動涣觉，一定步數(shù)后一定會在入口相遇,此結論與情況1一致痴荐。
因此問題2的實現(xiàn)思路為:找到相遇點，然后分配指針分別從頭結點和相遇點出發(fā)向前移動旨枯，如果相遇則相遇點為入口點.代碼如下:
/**
* 查找環(huán)入口
*
* @return
*/
public SNode<T> findLoopStartNode() {
if (isEmpty()) {
return null;
}
SNode<T> slow = headNode;
SNode<T> fast = headNode;
while (slow != null && fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {//倆哥們相遇蹬昌，則返回true
break;
}
}
if (slow == null || fast == null || fast.next == null) return null;//沒有環(huán)則返回空
SNode<T> p = headNode;//從頭節(jié)點出發(fā)
SNode<T> q = slow;//從相遇點出發(fā)
while (p != q) {
p = p.next;
q = q.next;
}
return p;//相遇點為環(huán)入口
}
3.有了環(huán)入口,那么環(huán)大小就好說了，從相遇點開始遍歷就行:
/**
* 獲取環(huán)大小
* @return
*/
public int getLoopSize() {
if (isEmpty()) {
return 0;
}
SNode<T> slow = headNode;
SNode<T> fast = headNode;
while (slow != null && fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {//倆哥們相遇攀隔，則返回true
break;
}
}
if (slow == null || fast == null || fast.next == null) return 0;//沒有環(huán)則返0
int size = 1;//環(huán)size從1開始
SNode<T> temp = slow.next;//從相遇點出發(fā)
while (temp != slow) {
size++;
temp = temp.next;
}
return size;
}
4.求環(huán)鏈表的長度:環(huán)鏈表的長度為環(huán)大小和入口到頭節(jié)點距離的和:
/**
* 獲取頭節(jié)點到入口的距離
*
* @return
*/
public int getLoopEntryDistance() {
if (isEmpty()) {
return 0;
}
SNode<T> slow = headNode;
SNode<T> fast = headNode;
while (slow != null && fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {//倆哥們相遇皂贩，則返回true
break;
}
}
if (slow == null || fast == null || fast.next == null) return size();//沒有環(huán)則返回單鏈表長度
SNode<T> p = headNode;//從頭節(jié)點出發(fā)
SNode<T> q = slow;//從相遇點出發(fā)
int distance = 0;
while (p != q) {
distance++;
p = p.next;
q = q.next;
}
return distance;
}
/**
* 獲得帶環(huán)鏈表大小
* @return
*/
public int getLoopLinkedListSize(){
return getLoopSize() + getLoopEntryDistance();
}
5.對面節(jié)點問題栖榨。環(huán)上距離節(jié)點最遠的節(jié)點為對面節(jié)點，如圖1和4明刷、2和5婴栽、3和6為對面節(jié)點，且距離最大為環(huán)大小的一半辈末。思路如下：判斷節(jié)點是否在環(huán)上愚争，如果在環(huán)上從當前節(jié)點前移環(huán)大小一半的步數(shù).
/**
* 獲得對面節(jié)點
*
* @return
*/
public SNode<T> getOppositeNode(SNode<T> node) {
boolean isLoop = false;
if (isEmpty() || node == null) {
return null;
}
boolean isOnLoop = false;
//判斷節(jié)點是否在環(huán)上
SNode<T> startNode = findLoopStartNode();
if (startNode == null) {//沒有環(huán)，返回空
return null;
}
int loopSize = getLoopSize();
for (int i = 0; i < loopSize; i++) {
if (node == startNode) {
isOnLoop = true;
break;
}
startNode = startNode.next;
}
SNode<T> temp = node;
if (isOnLoop) {
//走環(huán)一半步數(shù)
for (int i = 0; i < loopSize / 2; i++) {
temp = temp.next;
}
}
return temp;
}
6.對于倆擴展問題挤聘，可以這樣理解:加入鏈表A和B有交點轰枝，那么將其中一個鏈表首尾相連，那么另一個鏈表上必然會出現(xiàn)環(huán)组去，問題就轉化成問題一鞍陨，這里不在贅述。
總結:關于單鏈表从隆，最核心的操作就是玩轉節(jié)點的遍歷诚撵、斷開和連接操作，這四篇博客基本涵蓋了單鏈表的大部分操作键闺，為什么花費如此多的精力去學習它呢?因為它是基礎寿烟，包含了節(jié)點操作的基本思想，熟悉了它辛燥，后面的雙向鏈表筛武、棧、隊列就相對容易购桑。當然畅铭，還是那句話：學習數(shù)據(jù)結構就是學習思想。一沙一世界勃蜘，單鏈表也有很多東西可以發(fā)掘硕噩！關于單鏈表的學習暫時告一段落，如有紕漏歡迎指正缭贡！
