在鏈表中，不光只有普通的單鏈表。之前寫(xiě)過(guò)的的一個(gè)約瑟夫環(huán)形鏈表是尾直接連向頭的。這里的環(huán)形鏈表是從尾節(jié)點(diǎn)的next指針連向這鏈表的任意位置。

那么給定一個(gè)鏈表，判斷這個(gè)鏈表是否帶環(huán)。qj題141.環(huán)形鏈表就是一個(gè)這樣的題目。

這里的思路是用快慢指針，慢指針一次走一步快指針一次走兩步。兩個(gè)指針都從起始位置出發(fā)，帶環(huán)就一定會(huì)相遇，否則快指針率先走到鏈表的末尾。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {ListNode* slow=head,*fast=head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){return true;}}return false;
}

那么這里有兩個(gè)問(wèn)題。
1、為什么快指針走兩步，慢指針走一步就一定會(huì)相遇。
2、快指針一次走3步、4步…n步可以嗎?

1、為什么快指針走兩步，慢指針走一步就一定會(huì)相遇
又可能在慢指針剛?cè)氕h(huán)時(shí)就和快指針相遇了。慢指針叫slow，快指針叫fast，假設(shè)slow進(jìn)環(huán)時(shí)，fast與slow的距離為N時(shí)，這里fast走兩個(gè)slow走一個(gè)。
N-2+1 N-1
N-4+2 N-2
N-6+3 N-3
也就是說(shuō)每追及一次，距離就縮小1，當(dāng)距離為0時(shí)就追上了。

2、快指針一次走3步、4步…n步可以嗎?

假設(shè)slow進(jìn)環(huán)時(shí)，fast與slow的距離時(shí)N。fast走3個(gè)slow走1個(gè)。
N
N-2
N-4
這里要思考一下，如果N為偶數(shù)或奇數(shù)是否有不同？
當(dāng)N為偶數(shù)時(shí)，假設(shè)N為4，4-2為2 4-4為0這時(shí)就追上了。
當(dāng)N為奇數(shù)時(shí)，假設(shè)N為5，3 1 -1這時(shí)就錯(cuò)過(guò)了，進(jìn)行新一輪的追擊。
這時(shí)候fast和slow的距離就變成了c-1，c為環(huán)的長(zhǎng)度。
當(dāng)c-1為偶數(shù)的時(shí)候，下一輪就追不上。
當(dāng)c-1為奇數(shù)時(shí)下一輪就追的上。
c-1為偶數(shù)時(shí)之所以能追上，是因?yàn)楫?dāng)fast和slow都走起來(lái)時(shí)相對(duì)位移是2，所以為偶數(shù)時(shí)下一輪就追上了。
這里總結(jié)一下：
N時(shí)偶數(shù)，第一輪就追上了。
N時(shí)奇數(shù)，第一輪就會(huì)錯(cuò)過(guò)，距離變成c-1。
如果c-1為偶數(shù)的時(shí)候，下一輪就追上了。
如果c-1為奇數(shù)的時(shí)候，永遠(yuǎn)也追不上。
同時(shí)存在N為奇數(shù)且C時(shí)偶數(shù)，那么就永遠(yuǎn)追不上。

真的永遠(yuǎn)追不上嗎？

假設(shè)從初始位置到進(jìn)入環(huán)的距離為L(zhǎng)，fast與slow的距離為N。環(huán)的長(zhǎng)度為N。
slow走的距離為：L
fast走的距離為：L+nC+C-N
不確定fast是否只走不到一圈，也可能走了好幾圈所以用nC。

fast走的距離是slow的三倍
3L=L+xC+C-N
2*L=（x+1）*C-N

當(dāng)2L為偶數(shù)的時(shí)候，（x+1）偶數(shù)C-偶數(shù)N時(shí)，2L才為偶數(shù)。
當(dāng)2L為奇數(shù)的時(shí)候，（x+1）奇數(shù)C-奇數(shù)N時(shí)，2L才為奇數(shù)。
N是奇數(shù)時(shí)，C也是奇數(shù)
N是偶數(shù)時(shí)，C也是偶數(shù)
反證出，N為奇數(shù)且C為偶數(shù)不能同時(shí)存在，永遠(yuǎn)追不上的條件不成立。所以上面的結(jié)論不成立。

正確結(jié)論：
一定能追上。
N為偶數(shù)第一輪就追上了。
N為奇數(shù)第一輪追不上，第二輪C-1為偶數(shù)時(shí)就追上了