快慢指針技巧匯總

1、2425;快慢指針技巧匯總雙指針技巧可以分為兩類：一類是【快慢指針】、一類是【左右指針】、快慢指針快慢指針一般初始化指向鏈表頭結(jié)點(diǎn)head，前進(jìn)時(shí)快指針fast在前，慢指針slow在后，巧妙解決鏈表中的一些問(wèn)題。1、判斷鏈表中是否有環(huán)經(jīng)典解法就是用兩個(gè)指針，一個(gè)每次前進(jìn)兩步，一個(gè)每次前進(jìn)一步。如果不含有環(huán)，跑得快的那個(gè)指針最終會(huì)遇到null，說(shuō)明鏈表不含環(huán)；如果含有環(huán)，快指針最終會(huì)超慢指針一圈，和慢指針相遇，說(shuō)明鏈表含有環(huán)。*1/*Definitionforsingly-linkedlist.*structListNode*intval;*ListNode*next;*ListNode(int

2、x):val(x),next(NULL)*;*/classSolutionpublic:boolhasCycle(ListNode*head)ListNode*slow,*fast;slow=head;fast=head;while(fast!=NULL&fast-next!=NULL)fast=fast-next-next;slow=slow-next;17if(fast=slow)returntrue;returnfalse;2、返回環(huán)的起始位置第一次相遇時(shí)，假設(shè)慢指針slow走了k步，那么快指針fast定走了2k步，也就是說(shuō)比slow多走了k步(也就是環(huán)的長(zhǎng)度)。設(shè)相遇點(diǎn)距環(huán)的起點(diǎn)的距離

3、為m,那么環(huán)的起點(diǎn)距頭結(jié)點(diǎn)head的距離為k-m,也就是說(shuō)如果從head前進(jìn)k-m步就能到達(dá)環(huán)起點(diǎn)。巧的是，如果從相遇點(diǎn)繼續(xù)前進(jìn)k-m步，也恰好到達(dá)環(huán)起點(diǎn)。classSolutionpublic:ListNode*detectCycle(ListNode*head)ListNode*slow,*fast;boolhascycle=false;/標(biāo)記鏈表中是否有環(huán)slow=head;fast=head;while(fast!=NULL&fast-next!=NULL)fast=fast-next-next;slow=slow-next;if(fast=slow)hascycle=true;bre

4、ak;if(hascycle)slow=head;while(slow!=fast)slow=slow-next;fast=fast-next;returnslow;elsereturnNULL;173、尋找鏈表的中點(diǎn)快指針一次前進(jìn)兩步，慢指針一次前進(jìn)一步，當(dāng)快指針到達(dá)鏈表盡頭時(shí)，慢指針就處于鏈表的中間位置。classSolutionpublic:ListNode*middleNode(ListNode*head)ListNode*slow,*fast;slow=head;fast=head;while(fast!=NULL&fast-next!=NULL)fast=fast-next-nex

5、t;slow=slow-next;returnslow;4、尋找鏈表的倒數(shù)第k個(gè)元素我們的思路還是使用快慢指針，讓快指針先走k步，然后快慢指針開(kāi)始同速前進(jìn)。這樣當(dāng)快指針走到鏈表末尾null時(shí)，慢指針?biāo)诘奈恢镁褪堑箶?shù)第k個(gè)鏈表節(jié)點(diǎn).*1/*Definitionforsingly-linkedlist.structListNodeintval;ListNode*next;ListNode(intx):val(x),next(NULL);*/classSolutionpublic:ListNode*getKthFromEnd(ListNode*head,intk)ListNode*slow,*fa

6、st;slow=head;fast=head;while(k-)fast=fast-next;while(fast!=NULL)fast=fast-next;slow=slow-next;returnslow;二、左右扌旨針左右指針在數(shù)組中實(shí)際是指兩個(gè)索引值，一般初始化為left=0,right=nums.length-1。1、二分查找(普通二分)intbinarySerarch(vector&nums,inttarget)intleft=0;intright=nums.size()-1;while(left1;if(numsmid=target)returnmid;elseif(numsmi

7、dtarget)left=mid+1;elseright=mid-1;return-1;2、兩數(shù)之和如果數(shù)組有序，就應(yīng)該想到雙指針技巧。這道題的解法有點(diǎn)類似二分查找，通過(guò)調(diào)節(jié)left和right可以調(diào)整sum的大小:inttwoSum(vector&nums,inttarget)intleft=0;intright=nums.size()-1;while(leftright)intnum=numsleft+numsright;67891011if(num=target)returnleft,right;elseright-;elseif(numtarget)left+;return;只3、反轉(zhuǎn)數(shù)組voidreverse(intnums)intleft=0;intright=nums.length-1;while(leftright)/swap(numsleft,numsright)inttemp=numsleft;numslef