連結清單是否有環問題看似簡單，但實際處理上有很多需要注意的，這個問題是非常高頻筆試面試題，記憶不牢固容易遺忘，可以認真看看學習一波！有個小夥伴就在某手面試中遇到了。
判斷連結清單是否有環
題目描述：
給定一個連結清單，判斷連結清單中是否有環。
如果連結清單中有某個節點，可以通過連續跟蹤 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;
}
}