給定一個(gè)單鏈表，判斷其中是否有環(huán)，已經(jīng)是一個(gè)比較老同時(shí)也是比較經(jīng)典的問題，在網(wǎng)上搜集了一些資料，
然后總結(jié)一下大概可以涉及到的問題，以及相應(yīng)的解法。
首先，關(guān)于單鏈表中的環(huán)，一般涉及到一下問題：
1.給一個(gè)單鏈表，判斷其中是否有環(huán)的存在；
2.如果存在環(huán)，找出環(huán)的入口點(diǎn)；
3.如果存在環(huán)，求出環(huán)上節(jié)點(diǎn)的個(gè)數(shù)；
4.如果存在環(huán)，求出鏈表的長度；
5.如果存在環(huán)，求出環(huán)上距離任意一個(gè)節(jié)點(diǎn)最遠(yuǎn)的點(diǎn)（對(duì)面節(jié)點(diǎn)）；
6.（擴(kuò)展）如何判斷兩個(gè)無環(huán)鏈表是否相交；
7.（擴(kuò)展）如果相交，求出第一個(gè)相交的節(jié)點(diǎn)；
下面，我將針對(duì)上面這七個(gè)問題一一給出解釋和相應(yīng)的代碼。
問題1.判斷是否有環(huán)（鏈表頭指針為head）
對(duì)于這個(gè)問題我們可以采用“快慢指針”的方法。就是有兩個(gè)指針fast和slow，開始的時(shí)候兩個(gè)指針都指向鏈表頭head，然后在每一步操作中slow向前走一步即：slow = slow->next，而fast每一步向前兩步即：fast = fast->next->next。由于fast要比slow移動(dòng)的快，如果有環(huán)，fast一定會(huì)先進(jìn)入環(huán)，而slow后進(jìn)入環(huán)。當(dāng)兩個(gè)指針都進(jìn)入環(huán)之后，經(jīng)過一定步的操作之后，二者一定能夠在環(huán)上相遇，并且此時(shí)slow還沒有繞環(huán)一圈，也就是說一定是在slow走完第一圈之前相遇。
代碼：
/**
* 1.判斷是否有環(huán)
* 對(duì)于這個(gè)問題我們可以采用“快慢指針”的方法。就是有兩個(gè)指針fast和slow，開始的時(shí)候兩個(gè)指針都指向鏈表頭head，然后在每一步
* 操作中slow向前走一步即：slow = slow->next，而fast每一步向前兩步即：fast = fast->next->next。
* 由于fast要比slow移動(dòng)的快，如果有環(huán)，fast一定會(huì)先進(jìn)入環(huán)，而slow后進(jìn)入環(huán)。當(dāng)兩個(gè)指針都進(jìn)入環(huán)之后，經(jīng)過一定步的操作之后
* 二者一定能夠在環(huán)上相遇，并且此時(shí)slow還沒有繞環(huán)一圈，也就是說一定是在slow走完第一圈之前相遇。
* @param head
* @return
*/
public boolean isHasLoop(Node head){
Node fast = head;
Node slow = head;
while(slow != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
//有環(huán)
return true;
}
}
//無環(huán)
return false;
}
問題2.如果存在環(huán)，找出環(huán)的入口點(diǎn)；
我結(jié)合著下圖講解一下：
從上面的分析知道，當(dāng)fast和slow相遇時(shí)，slow還沒有走完鏈表，假設(shè)fast已經(jīng)在環(huán)內(nèi)循環(huán)了n(1<= n)圈。環(huán)的長度為r， 假設(shè)slow走了s步，s=a+b,其中：a為從head到環(huán)入口點(diǎn)的長度，b為從環(huán)入口點(diǎn)到相遇點(diǎn)的長度，則fast由于每次比slow多走一步，則共走了2s步， 同時(shí)相當(dāng)于比slow多走了n圈環(huán)，即共走了：s + n*r步，即：
a+b+nr = 2(a+b)
化簡得：a=nr-b, 即: a=(n-1)r+r-b
這個(gè)式子的意義就是，一個(gè)慢指針slow1從鏈表頭出發(fā)，1個(gè)慢指針slow2從相遇點(diǎn)，即b點(diǎn)出發(fā)，slow1走到環(huán)入口時(shí)(路程為a)，slow2也剛好走到環(huán)入口（路程為(n-1)r+r-b：n-1個(gè)整圈加上r-b的路程)
/**
* 2.如果存在環(huán)，找出環(huán)的入口點(diǎn)
* 從上面的分析知道，當(dāng)fast和slow相遇時(shí)，slow還沒有走完鏈表，假設(shè)fast已經(jīng)在環(huán)內(nèi)循環(huán)了n(1<= n)圈。環(huán)的長度為r
* 假設(shè)slow走了s步，s=a+b,其中：a為從head到環(huán)入口點(diǎn)的長度，b為從環(huán)入口點(diǎn)到相遇點(diǎn)的長度，則fast由于每次比slow多走一步，則共走了2s步，
* 同時(shí)相當(dāng)于比slow多走了n圈環(huán)，即共走了：s + n*r步，即：
*
* a+b+nr = 2(a+b)
* 化簡得：a=nr-b, 即: a=(n-1)r+r-b
*
* 這個(gè)式子的意義就是，一個(gè)慢指針slow1從鏈表頭出發(fā)，1個(gè)慢指針slow2從相遇點(diǎn)，即b點(diǎn)出發(fā)，slow1走到環(huán)入口時(shí)(路程為a)，
* slow2也剛好走到環(huán)入口（路程為(n-1)r+r-b：n-1個(gè)整圈加上r-b的路程)
*
*
* @param head
* @return
*/
public Node getLoopFirstNode(Node head){
Node meet = null;
Node fast = head;
Node slow = head;
while (fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
meet = fast;
}
}
if (meet != null) {
Node slowFromHead = head;
while (slowFromHead != meet) {
slowFromHead = slowFromHead.next;
meet = meet.next;
}
return slowFromHead;
}
return null;
}
問題3.如果存在環(huán)，求出環(huán)上節(jié)點(diǎn)的個(gè)數(shù):
對(duì)于這個(gè)問題，我這里有兩個(gè)思路（肯定還有其它跟好的辦法）：
思路1：記錄下相遇節(jié)點(diǎn)存入臨時(shí)變量tempPtr，然后讓slow(或者fast，都一樣)繼續(xù)向前走slow = slow -> next；一直到slow == tempPtr; 此時(shí)經(jīng)過的步數(shù)就是環(huán)上節(jié)點(diǎn)的個(gè)數(shù)；
思路2： 從相遇點(diǎn)開始slow和fast繼續(xù)按照原來的方式向前走slow = slow -> next; fast = fast -> next -> next；直到二者再次項(xiàng)目，此時(shí)經(jīng)過的步數(shù)就是環(huán)上節(jié)點(diǎn)的個(gè)數(shù) 。
/**
* 3.如果存在環(huán)，求出環(huán)上節(jié)點(diǎn)的個(gè)數(shù)；
* 對(duì)于這個(gè)問題，我這里有兩個(gè)思路（肯定還有其它跟好的辦法）：
*
* 思路1：記錄下相遇節(jié)點(diǎn)存入臨時(shí)變量tempPtr，然后讓slow(或者fast，都一樣)繼續(xù)向前走slow = slow -> next；一直到slow == tempPtr;
* 此時(shí)經(jīng)過的步數(shù)就是環(huán)上節(jié)點(diǎn)的個(gè)數(shù)；
*
* 思路2： 從相遇點(diǎn)開始slow和fast繼續(xù)按照原來的方式向前走slow = slow -> next; fast = fast -> next -> next；直到二者再次項(xiàng)目，
* 此時(shí)經(jīng)過的步數(shù)就是環(huán)上節(jié)點(diǎn)的個(gè)數(shù) 。
*
* @param head
* @return
*/
public int getLoopLength(Node head){
int length = 0;
Node meet = null;
Node fast = head;
Node slow = head;
while (fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
meet = fast;
}
}
if (meet != null) {
Node temp = meet;
do{
meet = meet.next;
length++;
}
while (meet != temp);
}
return length;
}
問題4. 如果存在環(huán)，求出鏈表的長度：
鏈表長度L = 起點(diǎn)到入口點(diǎn)的距離 + 環(huán)的長度r;
已經(jīng)知道了起點(diǎn)和入口點(diǎn)的位置，那么兩者之間的距離很好求了吧！環(huán)的長度也已經(jīng)知道了，因此該問題也就迎刃而解了！
/**
* 4.如果存在環(huán)，求出鏈表的長度；
* 鏈表長度L = 起點(diǎn)到入口點(diǎn)的距離 + 環(huán)的長度r;
* 已經(jīng)知道了起點(diǎn)和入口點(diǎn)的位置，那么兩者之間的距離很好求了吧！環(huán)的長度也已經(jīng)知道了，因此該問題也就迎刃而解了！
*
* @param head
* @return
*/
public int getLinkTableLength(Node head){
int headToLoopFirstNodeLength = 0;
int loopLength = 0;
int linkTableLength = 0;
Node meet = null;
Node loopFirstNode = null;
Node fast = head;
Node slow = head;
while (fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
meet = fast;
}
}
if (meet != null) {
//找出環(huán)的第一個(gè)節(jié)點(diǎn)
Node slowFromHead = head;
while (slowFromHead != meet) {
slowFromHead = slowFromHead.next;
meet = meet.next;
}
//計(jì)算環(huán)的長度
loopFirstNode = slowFromHead;
do{
slowFromHead = slowFromHead.next;
loopLength++;
}
while (slowFromHead != loopFirstNode);
//從head到環(huán)第一個(gè)節(jié)點(diǎn)的距離
while(head != loopFirstNode){
headToLoopFirstNodeLength++;
}
linkTableLength = headToLoopFirstNodeLength + loopLength;
}
return linkTableLength;
}
問題5. 求出環(huán)上距離任意一個(gè)節(jié)點(diǎn)最遠(yuǎn)的點(diǎn)（對(duì)面節(jié)點(diǎn)）
如下圖所示，點(diǎn)1和4、點(diǎn)2和5、點(diǎn)3和6分別互為”對(duì)面節(jié)點(diǎn)“ ，也就是換上最遠(yuǎn)的點(diǎn)，我們的要求是怎么求出換上任意一個(gè)點(diǎn)的最遠(yuǎn)點(diǎn)。
對(duì)于換上任意的一個(gè)點(diǎn)ptr0, 我們要找到它的”對(duì)面點(diǎn)“，可以這樣思考：同樣使用上面的快慢指針的方法，讓slow和fast都指向ptr0，每一步都執(zhí)行與上面相同的操作（slow每次跳一步，fast每次跳兩步），
當(dāng)fast = ptr0或者fast = prt0->next的時(shí)候slow所指向的節(jié)點(diǎn)就是ptr0的”對(duì)面節(jié)點(diǎn)“。
為什么是這樣呢？我們可以這樣分析：
如上圖，我們想像一下，把環(huán)從ptro處展開，展開后可以是無限長的（如上在6后重復(fù)前面的內(nèi)容）如上圖。
現(xiàn)在問題就簡單了，由于slow移動(dòng)的距離永遠(yuǎn)是fast的一般，因此當(dāng)fast遍歷玩整個(gè)環(huán)長度r個(gè)節(jié)點(diǎn)的時(shí)候slow正好遍歷了r/2個(gè)節(jié)點(diǎn)，
也就是說，此時(shí)正好指向距離ptr0最遠(yuǎn)的點(diǎn)。
/**
* 5.如果存在環(huán)，求出環(huán)上距離任意一個(gè)節(jié)點(diǎn)最遠(yuǎn)的點(diǎn)（對(duì)面節(jié)點(diǎn)）；
* 對(duì)于換上任意的一個(gè)點(diǎn)ptr0, 我們要找到它的”對(duì)面點(diǎn)“，可以這樣思考：同樣使用上面的快慢指針的方法，讓slow和fast都指向ptr0，
* 每一步都執(zhí)行與上面相同的操作（slow每次跳一步，fast每次跳兩步），
*
* 當(dāng)fast = ptr0或者fast = prt0->next的時(shí)候slow所指向的節(jié)點(diǎn)就是ptr0的”對(duì)面節(jié)點(diǎn)“, 即當(dāng)fast剛好走一圈時(shí)，
* 這個(gè)時(shí)候fast和slow之間的距離最遠(yuǎn)，之后距離主鍵縮小直至相遇。
*
*/
public Node getFarestNode(Node cur){
Node fast = cur;
Node slow = cur;
do{
fast = fast.next.next;
slow = slow.next;
}
while(fast != cur);
return slow;
}
問題6.（擴(kuò)展）如何判斷兩個(gè)無環(huán)鏈表是否相交，和7（擴(kuò)展）如果相交，求出第一個(gè)相交的節(jié)點(diǎn)，
兩個(gè)鏈表相交只能是以下兩種情況：
a有環(huán)，b有環(huán)，相交時(shí)共享同一個(gè)環(huán)
a無環(huán)，b無環(huán)，
第一種相當(dāng)于分別算出各自環(huán)的一個(gè)點(diǎn)，如果一樣，則相交；
對(duì)于第二種無環(huán)鏈表是否相交問題，假設(shè)有連個(gè)鏈表listA和listB，如果兩個(gè)鏈表都無環(huán)，并且有交點(diǎn)，那么我們可以讓其中一個(gè)鏈表（不妨設(shè)是listA）的為節(jié)點(diǎn)連接到其頭部，這樣在listB中就一定會(huì)出現(xiàn)一個(gè)環(huán)。所以該問題轉(zhuǎn)化為：1.listA構(gòu)建一個(gè)環(huán)，2.判斷l(xiāng)istB是否有環(huán)，有則相交，無則不相交
因此我們將問題6和7分別轉(zhuǎn)化成了問題1和2.
看看下圖就會(huì)明白了：
/**
*
* 6.（擴(kuò)展）如何判斷兩個(gè)無環(huán)鏈表是否相交；
* 兩個(gè)鏈表相交只能是以下兩種情況：
* a有環(huán)，b有環(huán)，相交時(shí)共享同一個(gè)環(huán)
* a無環(huán)，b無環(huán)，
*
* 第一種相當(dāng)于分別算出各自環(huán)的一個(gè)點(diǎn)，如果一樣，則相交；
* 對(duì)于第二種無環(huán)鏈表是否相交問題，假設(shè)有連個(gè)鏈表listA和listB，如果兩個(gè)鏈表都無環(huán)，并且有交點(diǎn)，那么我們可以讓其中一個(gè)鏈表
* （不妨設(shè)是listA）的為節(jié)點(diǎn)連接到其頭部，這樣在listB中就一定會(huì)出現(xiàn)一個(gè)環(huán)。所以該問題轉(zhuǎn)化為：1.listA構(gòu)建一個(gè)環(huán)，2.判斷l(xiāng)istB是否有環(huán)，
* 有則相交，無則不相交
*
* 因此我們將問題6和7分別轉(zhuǎn)化成了問題1和2.
*
* @param head1
* @param head2
* @return
*/
public boolean isTwoLinkTableIntersect(Node head1, Node head2){
//list1 首尾連起來
Node tail1 = head1;
while(head1.next != null){
tail1 = tail1.next;
}
tail1.next = head1;
//判斷l(xiāng)ist2是否有環(huán)
return isHasLoop(head2);
}
/**
* 7.（擴(kuò)展）如果相交，求出第一個(gè)相交的節(jié)點(diǎn)
* 其實(shí)就是做一個(gè)問題的轉(zhuǎn)化：
*
* 假設(shè)有連個(gè)鏈表listA和listB，如果兩個(gè)鏈表都無環(huán)，并且有交點(diǎn)，那么我們可以讓其中一個(gè)鏈表（不妨設(shè)是listA）的為節(jié)點(diǎn)連接到其頭部，這樣在listB中就一定會(huì)出現(xiàn)一個(gè)環(huán)。
*
* 因此我們將問題6和7分別轉(zhuǎn)化成了問題1和2.
*
* @param head1
* @param head2
* @return
*/
public Node getTwoLinkTableIntersectNode(Node head1, Node head2){
//list1 首尾連起來
Node tail1 = head1;
while(head1.next != null){
tail1 = tail1.next;
}
tail1.next = head1;
return getLoopFirstNode(head2);
}
原地址：http://blog.csdn.net/doufei_ccst/article/details/10578315
