[[402783]]

本文轉(zhuǎn)載自微信公眾號(hào)「bigsai」，作者bigsai。轉(zhuǎn)載本文請(qǐng)聯(lián)系bigsai公眾號(hào)。

鏈表是否有環(huán)問(wèn)題看似簡(jiǎn)單，但實(shí)際處理上有很多需要注意的，這個(gè)問(wèn)題是非常高頻筆試面試題，記憶不牢固容易遺忘，可以認(rèn)真看看學(xué)習(xí)一波!當(dāng)然今天這兩題對(duì)應(yīng)力扣141和力扣142，有個(gè)小伙伴就在某手面試中遇到了。

判斷鏈表是否有環(huán)

問(wèn)題描述：

給定一個(gè)鏈表，判斷鏈表中是否有環(huán)。

如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過(guò)連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。

如果鏈表中存在環(huán)，則返回 true 。否則，返回 false 。

你能用 O(1)(即，常量)內(nèi)存解決此問(wèn)題嗎?

分析：

對(duì)于這個(gè)問(wèn)題，如果沒(méi)有內(nèi)存空間的限制，首先想到的就是使用哈希的方法，用一個(gè)哈希存儲(chǔ)節(jié)點(diǎn)，然后向下枚舉鏈表節(jié)點(diǎn)：

如果發(fā)現(xiàn)其中有在哈希中，那么就說(shuō)明有環(huán)返回true。

如果枚舉到最后結(jié)束，那就說(shuō)明沒(méi)有環(huán)

但是這樣并不滿足O(1)空間復(fù)雜度的要求，我們應(yīng)該怎么處理呢?

如果鏈表尾部有環(huán)，如果一個(gè)節(jié)點(diǎn)枚舉到后面會(huì)在閉環(huán)中不斷循環(huán)枚舉，那么怎么樣能高效判斷有環(huán)并且能快速終止呢?

有環(huán)，其實(shí)就是第二次、第三次走過(guò)這條路才能說(shuō)它有環(huán)，一個(gè)指針在不借助太多空間存儲(chǔ)狀態(tài)下無(wú)法有效判斷是否有環(huán)(有可能鏈表很長(zhǎng)、有可能已經(jīng)在循環(huán)了)，咱們可以借助 快慢指針(雙指針) 啊。

其核心思想就是利用兩個(gè)指針：快指針(fast)和慢指針(slow),它們兩個(gè)同時(shí)從鏈表頭遍歷鏈表，只不過(guò)兩者速度不同，如果存在環(huán)那么最終會(huì)在循環(huán)鏈表中相遇。

我們?cè)诰唧w實(shí)現(xiàn)的時(shí)候，可以快指針(fast)每次走兩步，慢指針(slow)每次走一步。如果存在環(huán)的話快指針先進(jìn)入環(huán)，慢指針后入環(huán)，在慢指針到達(dá)末尾前快指針會(huì)追上慢指針。

快慢指針如果有相遇那就說(shuō)明有環(huán)，如果快指針先為null那就說(shuō)明沒(méi)環(huán)。

具體實(shí)現(xiàn)代碼為：

/** 
 * Definition for singly-linked list. 
 * class ListNode { 
 *     int val; 
 *     ListNode next; 
 *     ListNode(int x) { 
 *         val = x; 
 *         next = null; 
 *     } 
 * } 
 */ 
public class Solution { 
    public boolean hasCycle(ListNode head) { 
        ListNode fast=head; 
        ListNode slow=fast; 
        while (fast!=null&&fast.next!=null) { 
            slow=slow.next; 
            fast=fast.next.next; 
            if(fast==slow) 
                return true; 
        } 
        return false;     
    } 
} 

提高：找到環(huán)的入口

給定一個(gè)鏈表，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。如果鏈表無(wú)環(huán)，則返回 null。

為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來(lái)表示鏈表尾連接到鏈表中的位置(索引從 0 開始)。如果 pos 是 -1，則在該鏈表中沒(méi)有環(huán)。注意，pos 僅僅是用于標(biāo)識(shí)環(huán)的情況，并不會(huì)作為參數(shù)傳遞到函數(shù)中。

說(shuō)明：不允許修改給定的鏈表。

你是否可以使用 O(1) 空間解決此題?

這題相比上一題又難了一些，因?yàn)槿绻湵沓森h(huán)，需要找到入口。

分析：

如果不考慮內(nèi)存使用，我肯定還會(huì)首先考慮哈希，將節(jié)點(diǎn)存著然后如果出現(xiàn)第二次則說(shuō)明有環(huán)并直接返回，實(shí)現(xiàn)的代碼也很簡(jiǎn)單，走投無(wú)路可以用這個(gè)方法：

/** 
 * Definition for singly-linked list. 
 * class ListNode { 
 *     int val; 
 *     ListNode next; 
 *     ListNode(int x) { 
 *         val = x; 
 *         next = null; 
 *     } 
 * } 
 */ 
public class Solution { 
    public ListNode detectCycle(ListNode head) { 
        int pos=-1; 
        Map<ListNode,Integer>map=new HashMap<ListNode, Integer>(); 
        ListNode team=head; 
        while (team!=null) 
        { 
            if(map.containsKey(team)){ 
                pos=map.get(team); 
                return team; 
            } 
            else  
                map.put(team,++pos); 
            team=team.next; 
        } 
        return null; 
    } 
} 

但是怎么使用O(1)的空間復(fù)雜度完成這個(gè)操作呢?上面一題的思路是使用快慢指針判斷是否有環(huán)，但是怎么鎖定環(huán)的入口呢?

這個(gè)題看起來(lái)是個(gè)算法題，實(shí)際上是個(gè)數(shù)學(xué)推理題。這題的關(guān)鍵也是快慢指針，不過(guò)需要挖掘更多的細(xì)節(jié) 。

回憶一下快慢指針能夠挖掘的細(xì)節(jié)：

知道慢指針走了x步，快指針走了2x步，但是僅僅知道這兩個(gè)條件還推導(dǎo)不出什么東西，我們能夠進(jìn)行的操作也只有用O(1)的方法進(jìn)行一些操作。不過(guò)這里面快慢指針和前面有點(diǎn)不同的是我們前面用一個(gè)頭結(jié)點(diǎn)開始計(jì)數(shù)。

我們還可以進(jìn)行什么操作?

既然知道相遇的這個(gè)點(diǎn)在環(huán)內(nèi)，那么我們可以用一個(gè)新的節(jié)點(diǎn)去枚舉一圈看看環(huán)的長(zhǎng)度是多少哇!

這里面，我們可以知道fast走的步數(shù)2x，slow走的步數(shù)x，以及環(huán)長(zhǎng)y。

我們知道，慢指針是第一次入環(huán)，但快指針可能已經(jīng)走了好幾圈，但是多走的步數(shù)一定是環(huán)的整數(shù)倍(不然不可能在同一個(gè)位置相遇)。

那么可以得到 快指針步數(shù)=慢指針步數(shù)+n圈環(huán)長(zhǎng)度。當(dāng)然這里n我暫時(shí)不知道是多少。換算成公式，那就是 2x=x+ny 消去一個(gè)x得到：x=ny。

上面的圖我也標(biāo)注快指針多走的是整數(shù)圈數(shù)。難點(diǎn)就在這里，需要變通：

快指針多走的x是環(huán)長(zhǎng)y的整數(shù)倍n，慢指針走的x也是環(huán)長(zhǎng)y的整數(shù)倍n。

那么這樣有什么用呢?

如果某個(gè)節(jié)點(diǎn)從起點(diǎn)出發(fā)，走到fast，slow交匯點(diǎn)走的是x步(n*y步)。此時(shí)，如果某個(gè)指針從fast，slow交匯點(diǎn)開始如果走環(huán)長(zhǎng)的整數(shù)倍，那么它到時(shí)候還會(huì)在原位置。

也就是說(shuō)從開始head節(jié)點(diǎn)team1走x步，從fast，slow交匯節(jié)點(diǎn)team2走x步，它們最終依然到達(dá)fast，slow交匯的節(jié)點(diǎn)，但是在枚舉的途中，一旦team1節(jié)點(diǎn)遍歷的到環(huán)內(nèi)，那么就和team2節(jié)點(diǎn)重合了，所以它們一旦相等那就是第一個(gè)交匯的點(diǎn)了。

具體實(shí)現(xiàn)依然要判斷是否有環(huán)，實(shí)現(xiàn)代碼為：

/** 
 * Definition for singly-linked list. 
 * class ListNode { 
 *     int val; 
 *     ListNode next; 
 *     ListNode(int x) { 
 *         val = x; 
 *         next = null; 
 *     } 
 * } 
 */ 
public class Solution { 
    public ListNode detectCycle(ListNode head) { 
        boolean isloop=false; 
        ListNode fast=new ListNode(0);//頭指針 
        ListNode slow=fast; 
        fast.next=head; 
        if(fast.next==null||fast.next.next==null) 
            return null; 
        while (fast!=null&&fast.next!=null) { 
            fast=fast.next.next; 
            slow=slow.next; 
            if(fast==slow) 
            { 
                isloop=true; 
                break; 
            } 
        } 
        if(!isloop)//如果沒(méi)有環(huán)返回 
            return null; 
        ListNode team=new ListNode(-1);//頭指針 下一個(gè)才是head 
        team.next=head; 
        while (team!=fast) { 
            team=team.next; 
            fast=fast.next; 
        } 
        return team; 
    } 
} 

總結(jié)

到此，這個(gè)問(wèn)題就介紹到這里，如果有想法歡迎留言，后面會(huì)繼續(xù)分享更多數(shù)據(jù)結(jié)構(gòu)與算法介紹以及重要題型，歡迎mark。