判斷單連結清單是否有環，有一個很簡單的算法，即快慢指針算法。
我們可以建立兩個指針，一個慢指針slow，一個快指針fast，都是從頭結點開始往後周遊。其中滿指針一次走一步，即
slow = slow->next;
，而快指針一次走兩步，即
fast = fast->next->next;
，如果連結清單有環，那麼這兩個指針必然會相遇，否則fast指針若先指向了
NULL
，那麼顯然連結清單是可以窮盡的，也就自然就沒有環了。
大家如果想練手可以去：https://leetcode-cn.com/problems/linked-list-cycle/
下面放上我的代碼：
/**
* Definition of singly-linked-list:
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: True if it has a cycle, or false
*/
bool hasCycle(ListNode * head) {
// do the null case
if(head == NULL) return false;
ListNode* fast = head;
ListNode* slow = head;
// 隻需判斷fast指針是否為空就行了，畢竟它走得快
while(fast != NULL)
{
slow = slow->next;
// 如果能走到空指針，則一定不是環
if(fast->next == NULL || fast->next->next == NULL) return false;
else fast = fast->next->next;
// the true case
if(slow == fast) return true;
}
return false;
}
};
網傳的判斷是否有環的方法還有窮舉法和hash表法，不過都沒快慢指針法這麼好，大家有興趣可以自行去了解一下。
好，既然我們已經學會如何判斷單連結清單是否有環了，那又如何找到這個環的入口位址呢？
其實啊，這也不難，隻要對上面那個算法進行一些補充就行了。
我們先來細緻地分析一下上面的快慢指針。
你們可以在紙上模拟一下，或者稍微想一想，就能發現，當快慢指針相遇的時候，慢指針要麼還沒走完一遍全程，要麼剛好走完全程，而且剛好走完全程的情況是這整個連結清單都是一個環。
我們直接讨論一般情況。看下圖，A為起點，B為環的入口節點，C為快慢指針相遇節點，中間的其餘節點均省略沒畫了。A到B的距離為
S
，B到C的距離為
t
，C到B的距離為
X
。
那麼，在兩個指針相遇的時候，
慢指針共走過的路程為（A->B->C）：s+t
快指針共走過的路程為（A->B->C->B->C）：s+t+x+t
而且因為快指針走過的速度是慢指針兩倍，是以：s+t+x+t = 2*(s+t)
是以可以得出，
x=s
這意味着，從A到B的距離和從C到B的距離是相同的！
那麼，如果我們在快慢指針相遇之後，讓慢指針繼續走下去，而同時讓另一個指針從A節點出發往B走，那麼它們倆相遇的那個節點，就一定會是B節點，即這個環的入口節點！
嘿嘿，大家可以試試這道題：https://leetcode-cn.com/problems/linked-list-cycle-ii/
我的代碼：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while(fast != NULL)
{
slow = slow->next;
if(fast->next == NULL || fast->next->next == NULL) return NULL;
else fast = fast->next->next;
if(fast == slow)
{
fast = head;
while(fast!=slow)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
}
return NULL;
}
};
用上面的方法，我們就可以很輕松地解決另一道題了，即：如何判斷兩個單連結清單是否相交，别小看這道題，這道題在有環的情況下就需要是用到上面剛剛學到的算法啦！詳解請看：https://blog.csdn.net/qq_32623363/article/details/87885938