[[402783]]

本文轉載自微信公眾號「bigsai」，作者bigsai。轉載本文請聯系bigsai公眾號。

鏈表是否有環問題看似簡單，但實際處理上有很多需要注意的，這個問題是非常高頻筆試面試題，記憶不牢固容易遺忘，可以認真看看學習一波!當然今天這兩題對應力扣141和力扣142，有個小伙伴就在某手面試中遇到了。

判斷鏈表是否有環

問題描述：

給定一個鏈表，判斷鏈表中是否有環。

如果鏈表中有某個節點，可以通過連續跟蹤 next 指針再次到達，則鏈表中存在環。

如果鏈表中存在環，則返回 true 。否則，返回 false 。

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

分析：

對于這個問題，如果沒有內存空間的限制，首先想到的就是使用哈希的方法，用一個哈希存儲節點，然后向下枚舉鏈表節點：

如果發現其中有在哈希中，那么就說明有環返回true。

如果枚舉到最后結束，那就說明沒有環

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

如果鏈表尾部有環，如果一個節點枚舉到后面會在閉環中不斷循環枚舉，那么怎么樣能高效判斷有環并且能快速終止呢?

有環，其實就是第二次、第三次走過這條路才能說它有環，一個指針在不借助太多空間存儲狀態下無法有效判斷是否有環(有可能鏈表很長、有可能已經在循環了)，咱們可以借助 快慢指針(雙指針) 啊。

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

我們在具體實現的時候，可以快指針(fast)每次走兩步，慢指針(slow)每次走一步。如果存在環的話快指針先進入環，慢指針后入環，在慢指針到達末尾前快指針會追上慢指針。

快慢指針如果有相遇那就說明有環，如果快指針先為null那就說明沒環。

具體實現代碼為：

/** 
 * 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;     
    } 
} 

提高：找到環的入口

給定一個鏈表，返回鏈表開始入環的第一個節點。如果鏈表無環，則返回 null。

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

說明：不允許修改給定的鏈表。

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

這題相比上一題又難了一些，因為如果鏈表成環，需要找到入口。

分析：

如果不考慮內存使用，我肯定還會首先考慮哈希，將節點存著然后如果出現第二次則說明有環并直接返回，實現的代碼也很簡單，走投無路可以用這個方法：

/** 
 * 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)的空間復雜度完成這個操作呢?上面一題的思路是使用快慢指針判斷是否有環，但是怎么鎖定環的入口呢?

這個題看起來是個算法題，實際上是個數學推理題。這題的關鍵也是快慢指針，不過需要挖掘更多的細節 。

回憶一下快慢指針能夠挖掘的細節：

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

我們還可以進行什么操作?

既然知道相遇的這個點在環內，那么我們可以用一個新的節點去枚舉一圈看看環的長度是多少哇!

這里面，我們可以知道fast走的步數2x，slow走的步數x，以及環長y。

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

那么可以得到 快指針步數=慢指針步數+n圈環長度。當然這里n我暫時不知道是多少。換算成公式，那就是 2x=x+ny 消去一個x得到：x=ny。

上面的圖我也標注快指針多走的是整數圈數。難點就在這里，需要變通：

快指針多走的x是環長y的整數倍n，慢指針走的x也是環長y的整數倍n。

那么這樣有什么用呢?

如果某個節點從起點出發，走到fast，slow交匯點走的是x步(n*y步)。此時，如果某個指針從fast，slow交匯點開始如果走環長的整數倍，那么它到時候還會在原位置。

也就是說從開始head節點team1走x步，從fast，slow交匯節點team2走x步，它們最終依然到達fast，slow交匯的節點，但是在枚舉的途中，一旦team1節點遍歷的到環內，那么就和team2節點重合了，所以它們一旦相等那就是第一個交匯的點了。

具體實現依然要判斷是否有環，實現代碼為：

/** 
 * 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)//如果沒有環返回 
            return null; 
        ListNode team=new ListNode(-1);//頭指針 下一個才是head 
        team.next=head; 
        while (team!=fast) { 
            team=team.next; 
            fast=fast.next; 
        } 
        return team; 
    } 
} 

總結

到此，這個問題就介紹到這里，如果有想法歡迎留言，后面會繼續分享更多數據結構與算法介紹以及重要題型，歡迎mark。