算法大全面試題數(shù)據(jù)結(jié)構(gòu)

1、目錄1單鏈表反轉(zhuǎn)找出單鏈表的倒數(shù)第4個(gè)元素找出單鏈表的中間元素刪除無(wú)頭單鏈表的一個(gè)節(jié)點(diǎn)兩個(gè)不交叉的有序鏈表的合并有個(gè)二級(jí)單鏈表，其中每個(gè)元素都含有一個(gè)指向一個(gè)單鏈表的指針。寫(xiě)程序把這個(gè)二級(jí)鏈表稱(chēng)一級(jí)單鏈表。單鏈表交換任意兩個(gè)元素(不包括表頭)&判斷單鏈表是否有環(huán)？如何找到環(huán)的“起始”點(diǎn)？如何知道環(huán)的長(zhǎng)度？判斷兩個(gè)單鏈表是否相交兩個(gè)單鏈表相交，計(jì)算相交點(diǎn)用鏈表模擬大整數(shù)加法運(yùn)算單鏈表排序13柵IJ除單鏈表中重復(fù)的元素首先寫(xiě)一個(gè)單鏈表的C#實(shí)現(xiàn)，這是我們的基石：publicclassLinkpublicLinkNext;publicstringData;publicLiiik(Liiiknext,

2、stringdata)this.Next=next;this.Data=data;其中，我們需要人為地在單鏈表前面加一個(gè)空節(jié)點(diǎn)，稱(chēng)其為headc例如，一個(gè)單鏈表是1-2-5,如圖所示：對(duì)一個(gè)單鏈表的遍歷如下所示:staticvoidMain(stringargs)Linkhead=GenerateLiiik();Linkcuit=head;while(cuit!=null)Console.WriteLine(cuiT.Data);cuit=cuiT.Next;這道題目有兩種算法，既然是要反轉(zhuǎn)，那么肯定是要破壞原有的數(shù)據(jù)結(jié)構(gòu)的：算法1：我們需要額外的兩個(gè)變量來(lái)存儲(chǔ)當(dāng)前節(jié)點(diǎn)curr的下一個(gè)節(jié)點(diǎn)ne

3、xt、再下一個(gè)節(jié)點(diǎn)nextnext:publicstaticLinkReverseLinkl(Linkhead)Linkcuit=head.Next;Linknext=null;Linknextnext=null;/ifnoelementsoronlyoneelementexistsif(cuit=null|cuiT.Next=null)returnhead;/I/23/4/5/ifmorethanoneelementwhile(cuiT.Next!=null)next=ciuT.Next;nextnext=next.Next;next.Next=head.Next;head.Next=nex

4、t;cuiT.Next=nextnext;returnhead;算法的核心是while循環(huán)中的5句話我們發(fā)現(xiàn)，cuit始終指向第1個(gè)元素。此外，出于編程的嚴(yán)謹(jǐn)性，還要考慮2種極特殊的情況：沒(méi)有元素的單鏈表，以及只有一個(gè)元素的單鏈表，都是不需要反轉(zhuǎn)的。算法2：自然是遞歸如果題目簡(jiǎn)化為逆序輸出這個(gè)單鏈表，那么遞歸是很簡(jiǎn)單的，在遞歸函數(shù)之后輸出當(dāng)前元素，這樣能確保輸出第N個(gè)元素語(yǔ)句永遠(yuǎn)在第N+1個(gè)遞歸函數(shù)之后執(zhí)行，也就是說(shuō)第N個(gè)元素永遠(yuǎn)在第N+1個(gè)元素之后輸出，最終我們先輸出最后一個(gè)元素，然后是倒數(shù)第2個(gè)、倒數(shù)第3個(gè)，直到輸出第1個(gè)：publicstaticvoidReverseLink2(Liii

5、khead)if(head.Next!=null)ReverseLiiik2(head.Next);Console.WriteLine(head.Next.Data);但是，現(xiàn)實(shí)應(yīng)用中往往不是要求我們逆序輸出(不損壞原有的單鏈表)，而是把這個(gè)單鏈表逆序(破壞型)。這就要求我們?cè)谶f歸的時(shí)候，還要處理遞歸后的邏輯。首先，要把判斷單鏈表有0或1個(gè)元素這部分邏輯獨(dú)立出來(lái)，而不需要在遞歸中每次都比較一次：publicstaticLinkReverseLink3(Linkhead)/ifnoelementsoronlyoneelementexistsif(head.Next=null|head.Next.

6、Next=null)retiinihead;head.Next=ReverseLink(head.Next);returnhead;我們觀測(cè)到：head.Next=ReverseLiiik(head.Next);這句話的意思是為ReverseLiiik方法生成的逆序鏈表添加一個(gè)空表頭。接下來(lái)就是遞歸的核心算法ReverseLink了：staticLinkReverseLink(Linkhead)if(head.Next=null)retiinihead;LinkrHead=ReverseLiiik(head.Next);head.Next.Next=head;head.Next=null;re

7、tiinirHead;算法的關(guān)鍵就在于遞歸后的兩條語(yǔ)句:head.Next.Next=head;/Ihead.Next=null;/2啥意思呢？畫(huà)個(gè)圖表示就是：這樣，就得到了一個(gè)逆序的單鏈表，我們只用到了1個(gè)額外的變量rHeado2找出單鏈表的倒數(shù)第4個(gè)元素這道題目有兩種算法，但無(wú)論哪種算法，都要考慮單鏈表少于4個(gè)元素的情況:第1種算法，建立兩個(gè)指針，第一個(gè)先走4步，然后第2個(gè)指針也開(kāi)始走，兩個(gè)指針步伐(前進(jìn)速度)一致。staticLinkGetLast4thOne(Liiikhead)Linkfirst=head;Linksecond=head;for(inti=0;i4;i+)if(fii

8、st.Next=null)thrownewException(HLessthan4elements11);first=first.Next;while(first!=null)first=first.Next;second=second.Next;returnsecond;第2種算法，做一個(gè)數(shù)組aiT4,讓我們遍歷單鏈表，把第0個(gè)、第4個(gè)、第8個(gè)第4N個(gè)扔到an0,把第1個(gè)、第5個(gè)、第9個(gè)第4N+1個(gè)扔到anl,把第2個(gè)、第6個(gè)、第10個(gè)第4N+2個(gè)扔到aiT2,把第3個(gè)、第7個(gè)、第11個(gè)第4N+3個(gè)扔到an3,這樣隨著單鏈表的遍歷結(jié)束，art中存儲(chǔ)的就是單鏈表的最后4個(gè)元素，找到帳后一個(gè)元素

9、對(duì)應(yīng)的ani,讓k=(i+l)%4,則ank就是倒數(shù)第4個(gè)元素。staticLinkGetLast4thOneByAiTay(Linkhead)Linkcuit=head;inti=0;LiiikaiT=newLink4;while(cuiT.Next!=null)aiTi=cuiT.Next;cuit=cuiT.Next;i=(i+1)%4;if(ani=null)tluownewException(uLessthan4elements”);retiunaixi;本題目源代碼下載：推而廣之，對(duì)倒數(shù)第K個(gè)元素，都能用以上2種算法找出來(lái)。3找出單鏈表的中間元素算法思想：類(lèi)似于上題，還是使用兩個(gè)指

10、針first和second,只是first每次走一步，second每次走兩步：staticLinkGetMiddleOne(Linkhead)Linkfirst=head;Linksecond=head;while(first!=null&first.Next!=null)first=first.Next.Next;second=second.Next;returnsecond;但是，這道題目有個(gè)地方需要注意，就是對(duì)于鏈表元素個(gè)數(shù)為奇數(shù)，以上算法成立。如果鏈表元素個(gè)數(shù)為偶數(shù)，那么在返回second的同時(shí)，還要返回second.Next也就是下一個(gè)元素，它倆都算是單鏈表的中間元素。下面是加強(qiáng)版的

11、算法，無(wú)論奇數(shù)偶數(shù)，一概通殺：staticvoidMain(stringargs)Linkhead=GenerateLiiik();boolisOdd=tine;Linkmiddle=GetMiddleOne(head,refisOdd);if(isOdd)Console.WriteLine(middle.Data);elseConsole.WriteLine(middle.Data);Console.WriteLine(middle.Next.Data);Console.ReadO;staticLinkGetMiddleOne(Linkhead,refboolisOdd)Linkfirst=

12、head;Linksecond=head;while(first!=null&first.Next!=null)first=first.Next.Next;second=second.Next;if(first!=null)isOdd=false;returnsecond;4一個(gè)單鏈表，很長(zhǎng)，遍歷一遍很慢，我們僅知道一個(gè)指向某節(jié)點(diǎn)的指針curr,而我們又想刪除這個(gè)節(jié)點(diǎn)。這道題目是典型的“貍貓換太子”，如下圖所示:如果不考慮任何特殊情況，代碼就2行：ciUT.Data=cuiT.Next.Data;ciurNext=curr.Next.Next;上述代碼由一個(gè)地方需要注意，就是如果要?jiǎng)h除的是最后

13、一個(gè)元素呢？那就只能從頭遍歷一次找到倒數(shù)第二個(gè)節(jié)點(diǎn)了。此外，這道題目的一個(gè)變身就是將一個(gè)環(huán)狀單鏈表拆開(kāi)（即刪除其中一個(gè)元素），此時(shí)，只要使用上面那兩行代碼就可以了，不需要考慮表尾。相關(guān)問(wèn)題：只給定單鏈表中某個(gè)結(jié)點(diǎn)p（非空結(jié)點(diǎn)），在p前面插入一個(gè)結(jié)點(diǎn)q。話說(shuō)，交換單鏈表任意兩個(gè)節(jié)點(diǎn)，也可以用交換值的方法。但這樣就沒(méi)意思了,所以，才會(huì)有第7題霸王硬上工的做法。&兩個(gè)不交叉的有序鏈表的合并有兩個(gè)有序鏈表，各自?xún)?nèi)部是有序的，但是兩個(gè)鏈表之間是無(wú)序的。算法思路：當(dāng)然是循環(huán)逐項(xiàng)比較兩個(gè)鏈表了，如果一個(gè)到了頭，就不比較了，直接加上去。注意，對(duì)于2個(gè)元素的Data相等（僅僅是Data相等哦，而不是相同的引用）

14、，我們可以把它視作前面的Data大于后面的Data,從而節(jié)省了算法邏輯。staticLinkMergeTvoLink(Liiikheadl,Linkhead2)Linkhead=newLink(nultIntl6.Minalue);Linkpre=head;Linkcuit=head.Next;LinkcuitI=headl;Linkcuit2=head2;/compareuntilonelinknuitotheendwhile(cuitI.Next!=null&curr2Next!=null)if(cuitI.Next.DataciUT2.Next.Data)curr=newLiiik(nu

15、ll,cunl.Next.Data);ciutI=cunl.Next;elsecurr=newLiiik(null,cuiT2.Next.Data);cuit2=cuiT2.Next;pre.Next=cuit;pre=pre.Next;/ifhead1miltotheendwhile(cuitI.Next!=null)cuit=newLink(null,cuitI.Next.Data);cuitI=cuit1.Next;pre.Next=cuit;pre=pre.Next;/ifhead2miltotheendwhile(cun*2.Next!=null)cuit=newLink(null,

16、cuiT2.Next.Data);cun2=cuiT2.Next;pre.Next=cuit;pre=pre.Next;returnhead;如果這兩個(gè)有序鏈表交叉組成了Y型呢，比如說(shuō)：這時(shí)我們需要先找出這個(gè)交叉點(diǎn)(圖中是11),這個(gè)算法參見(jiàn)第9題，我們這里直接使用第10道題目中的方法Getlntersecto然后局部修改上面的算法，只要其中一個(gè)鏈表到達(dá)了交叉點(diǎn)，就直接把另一個(gè)鏈表的剩余元素都加上去。如下所示：staticLinkMergeTvoLink2(Liiikheadl,Linkhead2)Linkhead=newLiiik(nultIntl6.Minalue);Linkpre=hea

17、d;Linkcuit=head.Next;Linkintersect=Getlntersect(headl5head2);Linkcunl=headl;Linkcuit2=head2;/compareuntilonelinknuitotheintersectwhile(cuitI.Next!=intersect&cun2.Next!=intersect)if(cuit1.Next.Datahead4,它們組成了一個(gè)二級(jí)單鏈表head：null-headl-head2-head3-head4-我們的算法思想是：進(jìn)行兩次遍歷，在外層用ciMl遍歷二級(jí)單鏈表head,在內(nèi)層用CIUT2遍歷每個(gè)單鏈表

18、：publicstaticLinkGenerateNewLiiik(CascadeLiiikhead)CascadeLinkcunl=head.NextHead;LinknewHead=cunl.Next;Linkcuit2=newHead;while(cuitI!=null)cun2.Next=cunl.Next.Next;wliile(cun2Next!=null)cuit2=cuiT2.Next;cunl=cuiTl.NextHead;returnnewHead;其中，cuiT2.Next=cunl.Next.Next;這句話是關(guān)鍵，它負(fù)責(zé)把上一個(gè)單鏈表的表尾和下一個(gè)單鏈表的非空表頭連接

19、起來(lái)。7單鏈表交換任意兩個(gè)元素（不包括表頭）先一次遍歷找到這兩個(gè)元素cuitI和cuit2,同時(shí)存儲(chǔ)這兩個(gè)元素的前驅(qū)元素prel和pre2o然后大換血publicstaticLinkSwitchPoints(Liiikhead、Linkp,Linkq)if(p=head|q=head)tluownewException(,rNoexchangewithhead”)；if(p=q)returnhead;/findpandqinthelinkLinkcuit=head;LinkcuitI=p;Linkcuit2=q;Linkprel=null;Linkpre2=null;intcount=0;wh

20、ile(cuit!=null)if(cuiT.Next=p)prel=cuit;count+;if(count=2)break;elseif(cuiT.Next=q)pre2=cuit;count+;if(count=2)break;cuit=cuiT.Next;cuit=ciUTl.Next;pre1.Next=cuit2;cuiTl.Next=cuiT2.Next;pre2.Next=cunl;cuiT2.Next=cuit;retiinihead;注意特例，如果相同元素，就沒(méi)有必要交換；如果有一個(gè)是表頭，就不交換。&判斷單鏈表是否有環(huán)？如何找到環(huán)的“起始”點(diǎn)？如何知道環(huán)的長(zhǎng)度?算法思想：

21、先分弗量否有環(huán)。為此我們建立兩個(gè)指針，從headei起向前跑，一個(gè)步長(zhǎng)為1,一個(gè)步長(zhǎng)為2,用while(直到步長(zhǎng)2的跑到結(jié)尾)檢查兩個(gè)指針是否相等，直到找到為止。staticboolJudgeCiicleExists(Liiikhead)Linkfirst=head;/IstepeachtimeLinksecond=head;/2stepseachtimewhile(second.Next!=null&second.Next.Next!=null)second=second.Next.Next;first=first.Next;if(second=first)retiuntme;retiini

22、false;那又如何知道環(huán)的長(zhǎng)度呢？根據(jù)上面的算法，在返回true的地方，也就是2個(gè)指針相遇處，這個(gè)位置的節(jié)點(diǎn)P肯定位于環(huán)上。我們從這個(gè)節(jié)點(diǎn)開(kāi)始先前走，轉(zhuǎn)了一圈肯定能回來(lái)：staticintGetCircleLength(Linkpoint)intlength=1;Linkcun*=point;while(cuiT.Next!=point)length+；cuit=cuiT.Next;returnlength;繼續(xù)我們的討論，如何找到環(huán)的“起始”點(diǎn)呢？延續(xù)上面的思路，我們?nèi)匀辉诜祷豻ee的地方P,計(jì)算一下從有環(huán)單鏈表的表頭head到P點(diǎn)的距離staticintGetLengtliFromHea

23、dToPoint（Liiikhead,Linkpoint）intlength=1;Linkcuit=head;while(cuit!=point)length+；cuit=cuiT.Next;returnlength;如果我們把環(huán)從p點(diǎn)“切開(kāi)”（當(dāng)然并不是真的切，那就破壞原來(lái)的數(shù)據(jù)結(jié)構(gòu)了），那么問(wèn)題就轉(zhuǎn)化為計(jì)算兩個(gè)相交“單鏈表”的交點(diǎn)（第10題）：一個(gè)單鏈表是從P點(diǎn)出發(fā)，到達(dá)P（個(gè)回圈），距離M；另一個(gè)單鏈表從有環(huán)單鏈表的表頭head出發(fā)，到達(dá)P,距離N。我們可以參考第10題的Getlntersect方法并稍作修改。privatestaticLinkFiiidIntersect(Liiikhe

24、ad)Linkp=null;/getthepointinthecircleboolresult=JudgeCircleExists(head,refp);if(!result)retiininull;LinkcuitI=head.Next;Linkcuit2=p.Next;/lengthfromheadtopintM=1;while(cuitI!=p)M+;cuitI=cuit1.Next;/ciiclelengthintN=1;while(cuit2!=p)N+；cuit2=cuiT2.Next;/recovercunl&cuit2cuitI=head.Next;cuit2=p.Next;/make2linkshavethesamedistancetotheintersectif(MN)for(iiiti=0;iM-N;i+)ciutI=cunl.Next;elseif(MN)for(iiiti=0;iN)for(iiiti=0;iM-N;i+)ciutI=cunl.Next;elseif(MN)for(iiiti=0;i99NU