如何判斷單連結串列中是否存在環，Java判斷單連結串列是否有環的兩種實現方法

1樓：匿名使用者

思路：寫一個函式int checkloop(struct node * flag)，引數傳遞連結串列中任意結點。遍歷這個連結串列 struct node * t;t=t->next;判斷退出條件 if(t==null)return 0;//不存在if(t==flag)return 1;//存在

j**a判斷單連結串列是否有環的兩種實現方法

2樓：偏偏喜歡您

給定一個單連結串列，試判斷該單連結串列有無存在環。解答：演算法的思想是設定兩個指標p, q，其中p每次向前移動一步，q每次向前移動兩步。

那麼如果單連結串列存在環，則p和q相遇；否則q將首先遇到null。假定單連結串列的長度為n，並且該單連結串列是環狀的，那麼第i次迭代時，p指向元素i mod n，q指向2i mod n。因此當i≡2i(mod n)時，p與q相遇。

而i≡2i(mod n) => (2i - i) mod n = 0 => i mod n = 0 => 當i=n時，p與q相遇。這裡一個簡單的理解是，p和q同時在操場跑步，其中q的速度是p的兩倍，當他們兩個同時出發時，p跑一圈到達起點，而q此時也剛好跑完兩圈到達起點。那麼當p與q起點不同呢？

假定第i次迭代時p指向元素i mod n，q指向k+2i mod n，其中0

如何判斷一個連結串列中是否有環？

3樓：雲間

設定兩個指標，開始都指向連結串列頭，然後其中一個指標每次向前走一步，另一個指標每次向前走兩步，如果快的遇到null了，證明該連結串列中沒有環，如果有環，快的指標每次都要比慢的多走一步，最終兩個指標會相遇，（注意：這裡快指標不會跳過慢指標而不相遇，因為它每次都只比慢指標多走一個單位）

bool judge(list *head)list *pfast = head;

list *pslow = head;

while(pfast-next != null && pfast-next-next != null){pfast = pfast-next-next;

pslow = pslow-next;