購(gòu)物網(wǎng)站支付功能怎么做有創(chuàng)意的網(wǎng)絡(luò)廣告案例
在鏈表中,不光只有普通的單鏈表。之前寫(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í)就追上了