轉(zhuǎn)載常見和鏈表相關(guān)的算法

1、.轉(zhuǎn)載 常見和鏈表相關(guān)的算法原文地址：常見和鏈表相關(guān)的算法 daniel一、鏈表排序鏈表排序和數(shù)組排序的思路類似，只是鏈表操作起來比較費(fèi)事，因?yàn)椴荒茈S機(jī)訪問，所以只能借助于類似于前置或后置插入，添加等概念來完成。下面給出了鏈表排序的幾種方法。輔助代碼：/單鏈表節(jié)點(diǎn)的定義typedef struct LinkNodeint val；struct LinkNode*next；LinkNode；/由一個(gè)數(shù)組創(chuàng)立單鏈表LinkNode*CreateListint A,int countifNULL=Areturn NULL；LinkNode*head=LinkNode*mallocsizeofLink

2、Node；head-val=A0；head-next=NULL；LinkNode*p=head；forint i=1；i count；+ip-next=LinkNode*mallocsizeofLinkNode；p-next-val=Ai；p-next-next=NULL；p=p-next；return head；/顯示該單鏈表void ShowListLinkNode*LLinkNode*p=L；printf%d,p-val；whilep-nextp=p-next；printf-%d,p-val；printfn；1.插入排序以從小到大排序?yàn)槔湵砼判蜃钊菀紫氲降氖遣迦肱判?，它的根本想法是從?/p>

3、一個(gè)節(jié)點(diǎn)開場(chǎng)，每次將一個(gè)節(jié)點(diǎn)放到結(jié)果鏈表，并保證每個(gè)節(jié)點(diǎn)參加到結(jié)果鏈表前后，結(jié)果鏈表都是有序的。每個(gè)節(jié)點(diǎn)在被鏈入結(jié)果鏈表時(shí)有三種情況：1該節(jié)點(diǎn)值比結(jié)果鏈表中的所有元素值都大，那么將該節(jié)點(diǎn)追加到結(jié)果鏈表的最后；2該節(jié)點(diǎn)值比結(jié)果鏈表中的所有元素值都小，那么將該節(jié)點(diǎn)插入到結(jié)果鏈表最前面；3該節(jié)點(diǎn)值在結(jié)果鏈表中處于中間位置，那么將該節(jié)點(diǎn)插入到適宜位置。下面是該算法思路的流程圖：代碼實(shí)現(xiàn)如下：LinkNode*SortLinkListInsertionLinkNode*head/鏈表空或鏈表只有一個(gè)節(jié)點(diǎn)，不必排序，直接返回原頭結(jié)點(diǎn)ifNULL=head|NULL=head-nextreturn head

4、；/我們從第二個(gè)節(jié)點(diǎn)進(jìn)展處理，第一個(gè)節(jié)點(diǎn)作為結(jié)果鏈表的初始節(jié)點(diǎn)LinkNode*r=head-next；LinkNode*tmp；head-next=NULL；/將結(jié)果鏈表末尾標(biāo)記為完畢whileNULL！=r/依次處理每一個(gè)節(jié)點(diǎn)ifr-val head-val/將該節(jié)點(diǎn)插到結(jié)果鏈表最前，并修改鏈表頭，同時(shí)注意輔助變量的使用tmp=r-next；r-next=head；head=r；r=tmp；else/否那么從鏈表頭部開場(chǎng)搜索，注意這里搜索完畢的條件是當(dāng)前被搜索節(jié)點(diǎn)不是最后一個(gè)節(jié)點(diǎn)LinkNode*p=head；whileNULL！=p-next/注意只有當(dāng)節(jié)點(diǎn)嚴(yán)格小于被搜索節(jié)點(diǎn)的下一節(jié)點(diǎn)的

5、值是，才將其插入到被搜索節(jié)點(diǎn)后/這樣能保證排序是穩(wěn)定的！ifr-val p-next-valtmp=r-next；r-next=p-next；p-next=r；r=tmp；continue；/注意跳出，開場(chǎng)處理下一個(gè)節(jié)點(diǎn)elsep=p-next；/此時(shí)，p是結(jié)果鏈表中的末尾節(jié)點(diǎn)，將被處理節(jié)點(diǎn)追加到其后ifNULL=p-nexttmp=r-next；r-next=NULL；p-next=r；r=tmp；/end else/end whileNULL！=rreturn head；2.選擇排序以從小到大排序?yàn)槔x擇排序的根本思想是每次從源鏈表中選取并移除一個(gè)最小的元素，追加到結(jié)果鏈表的尾部，直到源鏈

6、表變空為止。因此本算法的關(guān)鍵點(diǎn)在于如何從源鏈表中選取并移除一個(gè)最小的元素?？紤]到一般情況下，我們?cè)谝瞥湵碇械哪硞€(gè)元素時(shí)，需要知道它的前一個(gè)節(jié)點(diǎn)的指針我知道你在想那個(gè)trick，但我想我們還是用正統(tǒng)的方法吧，于是我們可以按照最小元素的出現(xiàn)位置分為兩種情況：最小元素是鏈表頭部節(jié)點(diǎn)和最小元素不是鏈表頭部節(jié)點(diǎn)。我們先找出鏈表中除頭結(jié)點(diǎn)外的最小值節(jié)點(diǎn)，然后再和頭節(jié)點(diǎn)的值比較，然后進(jìn)展處理。尋找除頭結(jié)點(diǎn)外的最小值節(jié)點(diǎn)的代碼可以很簡(jiǎn)潔，這也是為什么要分成這兩部分處理的原因。代碼實(shí)現(xiàn)如下：LinkNode*SortLinkListSelection2LinkNode*head/我們這里即使不進(jìn)展特殊情況處理

7、，代碼也能正常工作，可以代入檢查/ifNULL=head|NULL=head-next/return head；/LinkNode*p=NULL；/遍歷輔助變量LinkNode*pminpre=NULL；/指向源鏈表中除頭結(jié)點(diǎn)外的最小值節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)LinkNode L=0,NULL；/我們這里用了一個(gè)啞節(jié)點(diǎn)，它能簡(jiǎn)化后面的代碼LinkNode*Ltail=&L；/Ltail用于指向結(jié)果鏈表的最后一個(gè)節(jié)點(diǎn)whileNULL！=head&NULL！=head-next/循環(huán)處理源鏈表中節(jié)點(diǎn)個(gè)數(shù)不小于2個(gè)的情況pminpre=head；p=head-next；whileNULL！=p&NULL！=

8、p-next/找出源鏈表中除頭結(jié)點(diǎn)外的最小值節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)ifp-next-val pminpre-next-val/嚴(yán)格小于時(shí)才改變pminpre pminpre=p；p=p-next；ifhead-val=pminpre-next-val/和頭結(jié)點(diǎn)值進(jìn)展比較處理，值相等時(shí)，取頭結(jié)點(diǎn)Ltail=Ltail-next=head；head=head-next；elseLtail=Ltail-next=pminpre-next；pminpre-next=pminpre-next-next；Ltail=Ltail-next=head；/最后一個(gè)節(jié)點(diǎn)直接追加到結(jié)果鏈表的尾部Ltail-next=NUL

9、L；/設(shè)置結(jié)果鏈表的完畢標(biāo)記return L.next；注意上面if語句中的和=判斷，他們能使得鏈表的選擇排序是穩(wěn)定的排序。3.冒泡排序以從小到大排序?yàn)槔湵淼拿芭菖判虿惶孟耄饕遣惶每刂票容^邊界。這里我們用一個(gè)標(biāo)記指針end表示邊界，每完成一趟冒泡后，end會(huì)被向前移一下，直到完成N-1趟冒泡。冒泡需要比較并交換相鄰的節(jié)點(diǎn)，因此我們?cè)趯?shí)現(xiàn)中使用了pre，cur，n等指針分別表示當(dāng)前處理節(jié)點(diǎn)的前驅(qū)，當(dāng)前處理節(jié)點(diǎn)和下一節(jié)點(diǎn)。鏈表冒泡排序的實(shí)現(xiàn)如下：/asscending sort link list LinkNode*SortLinkListBubbleLinkNode*headifNUL

10、L=headreturn head；/init end pointer LinkNode*end=NULL；whiletrueLinkNode*n=head-next；ifn=endbreak；/這里單獨(dú)處理頭結(jié)點(diǎn)和第二個(gè)節(jié)點(diǎn)的比較，這是沒有啞頭節(jié)點(diǎn)的鏈表的一個(gè)優(yōu)勢(shì)ifn-val head-valhead-next=n-next；n-next=head；head=n；LinkNode*pre=head；LinkNode*cur=head-next；LinkNode*tmp；n=cur-next；whilen！=endifn-val cur-valtmp=n-next；cur-next=n-ne

11、xt；n-next=cur；pre-next=n；n=tmp；elsen=n-next；pre=pre-next；cur=cur-next；end=cur；return head；4.快速排序從小到大排序知道鏈表還可以快速排序是在筆試某公司時(shí)才發(fā)現(xiàn)的，當(dāng)時(shí)只看到了個(gè)QsortList什么的，而且是個(gè)填空題，當(dāng)時(shí)沒有思路，也沒有做出來，只記得那個(gè)QsortList帶了3個(gè)參數(shù)，還返回了個(gè)鏈接點(diǎn)指針?；貋砗蠹?xì)想了一陣，發(fā)現(xiàn)原理和數(shù)組的快速排序是一樣的，只是鏈表在處理指針時(shí)比較費(fèi)事，而且要保證排序后鏈表還是有序地鏈接在一起，不能出現(xiàn)掉鏈等情況，有些繞人。思路這樣，從鏈表中選取一個(gè)節(jié)點(diǎn)一般簡(jiǎn)單地取頭結(jié)

12、點(diǎn)，將其值作為pivot，將鏈表中剩余的節(jié)點(diǎn)分成兩個(gè)子鏈表，其中一個(gè)中的所有值都小于pivot，另一個(gè)中的所有值都不小于pivot，然后將這兩條鏈表分別鏈接到pivot節(jié)點(diǎn)的兩端。然后對(duì)于子鏈表分別進(jìn)展遞歸該過程，直到子鏈表中只有一個(gè)節(jié)點(diǎn)為止。下面給出了鏈表快速排序的一種實(shí)現(xiàn)方法，該實(shí)現(xiàn)沒有返回參數(shù)，鏈表頭也是通過引用方式傳入的。void QsortListLinkNode*&head,LinkNode*endifhead=NULL|head=endreturn；LinkNode*pivot=head；LinkNode*p=head-next；LinkNode*head1=NULL,*tail

13、1=NULL；LinkNode*head2=NULL,*tail2=NULL；whilep！=endifp-val pivot-valifhead1=NULLhead1=tail1=p；elsetail1-next=p；tail1=p；elseifhead2=NULLhead2=tail2=p；elsetail2-next=p；tail2=p；p=p-next；iftail1tail1-next=pivot；ifhead2pivot-next=head2；else pivot-next=end；iftail2tail2-next=end；ifhead1head=head1；else head=

14、pivot；QsortListhead,pivot；/這里是傳入head,而不能傳入head1，因?yàn)閔ead還可能被子調(diào)用修改/同樣這里傳入pivot-next而非head2，這樣才能保證最后鏈表是有序鏈在一起的QsortListpivot-next,end；調(diào)用QsortList時(shí)采用這樣的方式QsortListL,NULL；數(shù)組的快速排序是不穩(wěn)定的，原因是其實(shí)現(xiàn)時(shí)采用了交換的機(jī)制；而鏈表的快速排序那么是穩(wěn)定的，其原因是，被掃描的節(jié)點(diǎn)是有序地依次添加到子鏈表的末尾，保證了兩個(gè)等值節(jié)點(diǎn)的相對(duì)位置不變。二、關(guān)于鏈表的其他筆試面試題很多公司都考這個(gè)東西，其實(shí)考來考去本質(zhì)就是那幾道題，比較根底的東西

15、，弄懂了其他類似的略微變一下就行了。1.單鏈表倒置就是倒插法了，假想如今有一個(gè)空鏈表這是鏈表的一個(gè)很好的優(yōu)點(diǎn)，定義一個(gè)指針，你就可以聲稱創(chuàng)立了一個(gè)鏈表了，很節(jié)省空間，對(duì)輸入的鏈表，從頭到尾進(jìn)展掃描，把每個(gè)節(jié)點(diǎn)都插入到假想鏈表的頭部，然后返回假想的鏈表就可以，唯一需要注意的就是，邊界情況和完畢標(biāo)記的NULL指針。下面是一種實(shí)現(xiàn)：Node*reverseNode*headifNULL=headreturn head；Node*p=head-next；head-next=NULL；Node*tmp；whileNULL！=ptmp=p-next；p-next=head；head=p；p=tmp；ret

16、urn head；關(guān)于單鏈表的倒置，還有個(gè)遞歸的算法，雖然該算法在實(shí)際工作中沒有任何作用，除了應(yīng)付某些考試或僅僅作為一種談資之外當(dāng)然，也可以說是在啟發(fā)思維：Node*reverseNode*head,Node*preNode*p=head-next；head-next=pre；ifpreturn reversep,head；else return head；調(diào)用方式：reversehead,NULL；2.求鏈表的倒數(shù)第K個(gè)節(jié)點(diǎn)，假設(shè)K大于鏈表長(zhǎng)度那么返回NULL。這也是某公司的筆試題之一，出題者的意圖是不想讓做題者遍歷兩次鏈表，即你不能先數(shù)鏈表中到底有幾個(gè)節(jié)點(diǎn)。在不知道鏈表到底有幾個(gè)節(jié)點(diǎn)的前提

17、下找到倒數(shù)第K個(gè)節(jié)點(diǎn)，嗯，聽起來很酷，雖然可以先數(shù)數(shù)到底有多少個(gè)，做做減法，再去找順數(shù)第多少個(gè)實(shí)際上這個(gè)笨笨的方法和那個(gè)酷酷的方法進(jìn)展的機(jī)器操作數(shù)的差異根本可以忽略，只是在鏈表非常長(zhǎng)，而K值很小的情況下，笨方法需要再從頭來過，而酷方法可以每個(gè)節(jié)點(diǎn)過兩次，因此占到了部分性原理的廉價(jià)。說了這么多，還是看看實(shí)現(xiàn)吧，看了就明白了。Node*BackKthNode*head,int KifNULL=head|K=0return NULL；Node*pK=head；whileNULL！=pK&K 1/Note that head is the first NodepK=pK-next；K-；ifNULL=

18、pK/K LengthOfList return NULL；Node*p=head；whileNULL！=pK-next/Not the last Nodep=p-next；pK=pK-next；return p；3.求鏈表的第K個(gè)節(jié)點(diǎn)搞笑么?哪個(gè)公司會(huì)出這樣的題啊?呵呵，沒有公司會(huì)出這樣的題，我自己想的。只是為了下面可能用到，高手請(qǐng)?zhí)^。Node*KthNodeNode*head,int KifK=0return NULL；Node*p=head；whileNULL！=p&K 1p=p-next；K-；return p；4.不知道單鏈表節(jié)點(diǎn)前驅(qū)的情況下，刪除該節(jié)點(diǎn)被問到過這樣的問題，我笑而不

19、語。這只能算一個(gè)小小的trick，其方法就是將該節(jié)點(diǎn)的后繼結(jié)點(diǎn)中的值數(shù)據(jù)拷到本節(jié)點(diǎn)中，然后刪掉后繼節(jié)點(diǎn)。要是節(jié)點(diǎn)中的數(shù)據(jù)很多很龐大，而且還需要深拷貝呢?=。=！5.求單鏈表的中間節(jié)點(diǎn)，偶數(shù)個(gè)節(jié)點(diǎn)時(shí)返回中間兩個(gè)節(jié)點(diǎn)的前一個(gè)這是一個(gè)很經(jīng)典的問題。當(dāng)然也可以先數(shù)數(shù)鏈表中有多少個(gè)節(jié)點(diǎn)，然后遍歷一半，這很直接，但是不夠巧妙，相信也不會(huì)是提問者想要的答案。我們可以這樣考慮，設(shè)想兩個(gè)人跑步，一個(gè)人的速度是另外一個(gè)人的兩倍，當(dāng)速度快的人到達(dá)了終點(diǎn)，速度慢的人就在賽程的正中間。同樣地，我們?cè)O(shè)置兩個(gè)游動(dòng)的指針，慢的指針挪動(dòng)步長(zhǎng)為1，快的指針挪動(dòng)的步長(zhǎng)為2。一開場(chǎng)都指向鏈表的頭部，當(dāng)遍歷開場(chǎng)時(shí)，進(jìn)展這樣的操作：假設(shè)

20、快的指針可以向前挪動(dòng)兩步并且沒有到達(dá)鏈表的尾部的話，快指針就向前挪動(dòng)2個(gè)節(jié)點(diǎn)，同時(shí)慢的指針向前挪動(dòng)1個(gè)節(jié)點(diǎn)；否那么退出，返回慢指針。該算法的實(shí)現(xiàn)如下，注意區(qū)別鏈表長(zhǎng)度為偶數(shù)和奇數(shù)的情況：Node*FindMidNode*headifNULL=head|NULL=head-nextreturn head；Node*p1=head；Node*p2=head；whileNULL！=p2-next&NULL！=p2-next-nextp1=p1-next；p2=p2-next-next；return p1；如今把問題略微改變一下，變成偶數(shù)個(gè)節(jié)點(diǎn)時(shí)返回中間兩個(gè)節(jié)點(diǎn)的后一個(gè)。上面的算法中的循環(huán)需要略微調(diào)整

21、一下。前面的算法中，快指針p2每次都挪動(dòng)2步，而本問題中，我們需要改變下策略，變成：只要快指針p2能向前挪動(dòng)一步，那么快指針和慢指針就都同時(shí)向前挪動(dòng)一步，再看看快指針是否還能補(bǔ)上一步，假設(shè)能補(bǔ)上一步，那么就補(bǔ)上，然后進(jìn)展下一輪循環(huán)，否那么就表示到達(dá)了鏈表尾部，返回慢指針即可。實(shí)現(xiàn)如下：Node*FindMin2Node*headifNULL=head|NULL=head-nextreturn head；Node*p1=head；Node*p2=head；whileNULL！=p2-nextp2=p2-next；p1=p1-next；ifNULL=p2-nextreturn p1；else p2

22、=p2-next；return p1；這種步長(zhǎng)法的想法很巧妙，后面的題中還會(huì)使用。6.判斷單鏈表是否有環(huán)，并求出環(huán)開場(chǎng)的節(jié)點(diǎn)，參考1。假設(shè)沒有環(huán)，就返回NULL。如以以下圖中所示，該單鏈表環(huán)開場(chǎng)的節(jié)點(diǎn)是3。首先，我們判斷單鏈表是否有環(huán)，這里我們也借用了步長(zhǎng)法，即指針p1，p2都指向鏈表頭，然后開場(chǎng)遍歷，p1每次挪動(dòng)一步，p2每次挪動(dòng)兩步，然后判斷p2有沒有遇到p1。假設(shè)遇到了p1，說明鏈表有環(huán)；假設(shè)遇到之前，p2就已經(jīng)到達(dá)鏈表尾部值為NULL，說明鏈表沒有環(huán)。判斷單鏈表是否有環(huán)算法的實(shí)現(xiàn)如下：BOOL FindCirleStartLinkNode*LLinkNode*p1=L；LinkNode

23、*p2=L；whileNULL！=p2-nextp2=p2-next；ifNULL=p2-next/Not acyclic link listreturn FALSE；p2=p2-next；p1=p1-next；ifp1=p2return TRUE；return FALSE；如何證明這個(gè)算法的正確性?p2最多要繞環(huán)轉(zhuǎn)幾圈才能追上p1?關(guān)于這一點(diǎn)可以參考1中的證明，這里也再轉(zhuǎn)述下。上面的圖是鏈表有環(huán)時(shí)的示意圖，原作者沒有把它化成鏈表構(gòu)造，而只是以連續(xù)的線條代替，我們?cè)诳紤]問題的時(shí)候需要注意到它們是離散的節(jié)點(diǎn)。下面就詳細(xì)分析該算法的思路：a.假設(shè)鏈表無環(huán)，我們的算法是能得到正確的結(jié)果的；b.這里我

24、們考慮鏈表有環(huán)的情況。按照算法的流程，當(dāng)慢指針p1，到達(dá)環(huán)開場(chǎng)節(jié)點(diǎn)A時(shí)，此時(shí)快節(jié)點(diǎn)必定在環(huán)中的某個(gè)節(jié)點(diǎn)，我們假設(shè)為B。這里我們只是隨意假設(shè)B而已，B可能在環(huán)中的任意位置，也有可能就是節(jié)點(diǎn)A那樣的話，算法就直接得到結(jié)果了。我們假設(shè)指針以順時(shí)針方向在環(huán)中挪動(dòng)，B間隔 A的長(zhǎng)度為y個(gè)節(jié)點(diǎn)，可以認(rèn)為B處的快指針p2落后于A處的快指針p1的間隔 為y0=y LengthOfCircle個(gè)節(jié)點(diǎn)。如今開場(chǎng)賽跑，每輪循環(huán)快指針p2向前跑2個(gè)節(jié)點(diǎn)，慢指針p1向前跑1個(gè)節(jié)點(diǎn)，兩者綜合起來的效果就是快指針和慢指針的間隔 減少1個(gè)節(jié)點(diǎn)，因此經(jīng)過y輪循環(huán)之后，兩指針將相遇，且相遇點(diǎn)為A向前y個(gè)節(jié)點(diǎn)的M點(diǎn)。因此證明了上述

25、算法是正確的。下面我們?cè)賮砜纯醋髡呤窃鯓忧蟪霏h(huán)開場(chǎng)的節(jié)點(diǎn)A，順便計(jì)算出環(huán)的長(zhǎng)度的。在前面的證明中，我們是從慢指針到達(dá)A點(diǎn)開場(chǎng)證明的，而忽略了前面從鏈表頭到A點(diǎn)的x個(gè)間隔 。如今假設(shè)慢指針從鏈表頭head到達(dá)A點(diǎn)時(shí)，快指針p2已經(jīng)挪動(dòng)到了B點(diǎn)，設(shè)環(huán)長(zhǎng)為s個(gè)節(jié)點(diǎn)，那么有關(guān)系式：2x=x+n*s+s-y。即x=n+1s y。當(dāng)慢指針p1和快指針p2同時(shí)到達(dá)M點(diǎn)時(shí)，即到達(dá)前面證明的最后時(shí)，我們?cè)僭黾酉旅嬉恍┎僮鳎毫砥鹨粋€(gè)指針p從鏈表頭head開場(chǎng)挪動(dòng)，每次挪動(dòng)一個(gè)節(jié)點(diǎn)，同樣慢指針p1也繼續(xù)從M點(diǎn)向前挪動(dòng)。當(dāng)p經(jīng)過x步到達(dá)A時(shí)，p1也經(jīng)過n*s+s-y到達(dá)A點(diǎn)，和p相遇，這樣我們就找到了A點(diǎn)。在此過程中

26、，我們可以同時(shí)記下p1反復(fù)經(jīng)過M點(diǎn)的次數(shù)n，然后利用s=x+y/n+1計(jì)算環(huán)的長(zhǎng)度。注意，我們無法直接單獨(dú)得到x或y的值，但卻能統(tǒng)計(jì)從head開場(chǎng)到慢指針p1和快指針p2第一次在M點(diǎn)相遇時(shí)經(jīng)過的循環(huán)次數(shù)x+y。下面的實(shí)現(xiàn)中表達(dá)了這一點(diǎn)：LinkNode*FindCirleStartLinkNode*L,int&nCircleLenLinkNode*p1=L；LinkNode*p2=L；int xy=0；/x+y whileNULL！=p2-nextp2=p2-next；ifNULL=p2-next/Not acyclic link listreturn NULL；p2=p2-next；p1=p

27、1-next；xy+；ifp1=p2LinkNode*M=p2；LinkNode*p=L；int n=0；whilep！=p1p=p-next；p1=p1-next；ifp1=Mn+；nCircleLen=xy/n+1；return p；/此時(shí)的p即為A點(diǎn)return NULL；另一種求環(huán)長(zhǎng)的方法：當(dāng)p1和p2第一次在M相遇時(shí)，我們已經(jīng)知道了鏈表是有環(huán)的了，所以還可以通過一種簡(jiǎn)單的計(jì)數(shù)方法求環(huán)的長(zhǎng)度，即用指針遍歷環(huán)一圈，直到重新回到M點(diǎn)。只是這樣，我們是無法得到環(huán)開場(chǎng)的節(jié)點(diǎn)A的。不難證明，以上算法的復(fù)雜度是線性的。下面給出一個(gè)引申的問題，該問題也是類似，可以在線性時(shí)間內(nèi)解決：假設(shè)一個(gè)單鏈表可能

28、有環(huán)，如何計(jì)算該鏈表的長(zhǎng)度?可以通過前面的方法判斷是否有環(huán)，找到環(huán)開場(chǎng)節(jié)點(diǎn)A，并求出環(huán)長(zhǎng)度。然后再計(jì)算從鏈表頭head到A的間隔 ，然后做計(jì)算。7.判斷兩個(gè)單鏈表是否相交，假設(shè)相交那么返回交點(diǎn)的指針，否那么返回NULL。這是?編程之美?上面的一個(gè)題，關(guān)于這個(gè)問題，一般的討論都是基于無環(huán)單鏈表的，即第1種情況，這里我們也討論第2種情況，即單鏈表存在環(huán)的情況，最后我們也討論下，不知道到底屬于那種情況下的解決方法。1無環(huán)情況無交點(diǎn)有交點(diǎn)如上兩圖中分別顯示了兩單鏈表無環(huán)的情況下，無交點(diǎn)和有交點(diǎn)的情況。無環(huán)情況的判斷和求交點(diǎn)都比較簡(jiǎn)單。判斷的思路如下：分別找到L1鏈表和L2鏈表的最后一個(gè)節(jié)點(diǎn)，判斷它們是

29、不是同一個(gè)節(jié)點(diǎn)，假設(shè)是同一個(gè)節(jié)點(diǎn)，那么就兩鏈表就是相交的；假設(shè)是不同的兩節(jié)點(diǎn)，就是不相交的。求交點(diǎn)思路有些巧妙：在判斷是否存在交點(diǎn)遍歷兩鏈表的時(shí)候，我們可以順便分別計(jì)算兩鏈表的長(zhǎng)度，然后計(jì)算其長(zhǎng)度差d，再分別從短鏈表和長(zhǎng)鏈表的第d個(gè)節(jié)點(diǎn)開場(chǎng)遍歷并判斷兩者是否相等，第一個(gè)相等的節(jié)點(diǎn)指針就是交點(diǎn)指針。實(shí)現(xiàn)如下：/Return NULL if there no crossing node Node*FindCrossingNodeNoLoopNode*head1,Node*head2ifNULL=head1|NULL=head2return NULL；int Len1=1；Node*p1=head1

30、；whileNULL！=p1-nextLen1+；p1=p1-next；int Len2=1；Node*p2=head2；whileNULL！=p2-nextLen2+；p2=p2-next；ifp1！=p2/Different ending Node,no crossing node return NULL；p1=head1；p2=head2；ifLen1 Len2int K=Len1 Len2；whileK 0p1=p1-next；K-；else ifLen1 Len2int K=Len2 Len1；whilek 0p2=p2-next；K-；whilep1！=p2p1=p1-next；p

31、2=p2-next；return p1；2有環(huán)情況無交點(diǎn)情況1和無交點(diǎn)情況2分別顯示了一條及兩條鏈表有環(huán)時(shí)，不相交的情況，這兩種情況在設(shè)計(jì)算法時(shí)需要做一些考慮。無交點(diǎn)情況1無交點(diǎn)情況2有交點(diǎn)情況1顯示了環(huán)在交點(diǎn)后面的情況。有交點(diǎn)情況1有交點(diǎn)情況2顯示了交點(diǎn)是環(huán)開場(chǎng)的節(jié)點(diǎn)的情況。有交點(diǎn)情況2有交點(diǎn)情況3顯示了鏈表交點(diǎn)在環(huán)中間的情況。這種情況比較復(fù)雜，此時(shí)我們既可以認(rèn)為交點(diǎn)是A節(jié)點(diǎn)，也可以認(rèn)為交點(diǎn)是B節(jié)點(diǎn)。假設(shè)我們把環(huán)看成是L2的，那么就是L1交L2于A點(diǎn)；假設(shè)我們把環(huán)看成L1的，那么就是L2交L1于B點(diǎn)。實(shí)際上，這個(gè)環(huán)也是L1和L2共有的。因此此種情況下A和B都是鏈表的交點(diǎn)，我們只能通過間隔 遠(yuǎn)

32、近來分辨了。間隔 L1較近的交點(diǎn)是A，間隔 L2較近的焦點(diǎn)是B。這個(gè)問題具有對(duì)稱性，后面我們會(huì)利用該性質(zhì)。有交點(diǎn)情況3如何判斷有環(huán)情況下鏈表是否存在交點(diǎn)，并求出交點(diǎn)，這個(gè)問題似乎比較復(fù)雜，我們不能直接使用無環(huán)情況下的算法了，因?yàn)槲覀儫o法進(jìn)展鏈表完畢判斷。不過，假設(shè)我們將其轉(zhuǎn)化無環(huán)情況的話，就能使用已有的算法了。想想我們之前找到有環(huán)鏈表的環(huán)開場(chǎng)節(jié)點(diǎn)，以及求環(huán)長(zhǎng)度的算法，這里我們可以直接利用。知道環(huán)開場(chǎng)節(jié)點(diǎn)和環(huán)長(zhǎng)度后，我們就可以找到環(huán)的末節(jié)點(diǎn)理論上，環(huán)是沒有末節(jié)點(diǎn)的，這里的末節(jié)點(diǎn)就是環(huán)開場(chǎng)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，然后斷開環(huán)。下面是有交點(diǎn)情況1和2斷開環(huán)后的示意圖，實(shí)際上除了環(huán)開場(chǎng)節(jié)點(diǎn)和交點(diǎn)的相對(duì)位置不同外

33、，這兩種情況可以歸為一種類型：兩鏈表環(huán)開場(chǎng)節(jié)點(diǎn)一樣。有交點(diǎn)情況1斷開后有交點(diǎn)情況2斷開后對(duì)于有交點(diǎn)情況3，它屬于另一種類型：兩鏈表的環(huán)開場(chǎng)節(jié)點(diǎn)不同。對(duì)于該種類型，我們有兩種斷開方法，一種是選擇斷開L1的環(huán)，另一種選擇是斷開L2的環(huán)。實(shí)際上，由于兩鏈表是共享環(huán)的，所以隨意從哪個(gè)鏈表斷開環(huán)，另外一個(gè)鏈表中的環(huán)也就自動(dòng)斷開了。下面是分別從L1和L2斷開環(huán)的情況：有交點(diǎn)情況3，從L1斷開環(huán)有交點(diǎn)情況3，從L2斷開環(huán)這里我再給出有交點(diǎn)情況3的另一種表達(dá)方式，它和前面的圖沒有什么區(qū)別，只是可能看起來舒適些：有交點(diǎn)情況3的等效圖因此我們不難看出，既可以說L1交L2于A，也可以說L2交L1于B。假設(shè)我們選擇斷

34、開L1，那么所求的交點(diǎn)為B，假設(shè)我們從L2斷開，那么所求交點(diǎn)為A。另外一點(diǎn)需要注意的是，我們?cè)贁嚅_環(huán)后，還要在適當(dāng)?shù)臅r(shí)候?qū)ζ溥M(jìn)展復(fù)原，即重置End的指針為Start節(jié)點(diǎn)的地址?；趩栴}的全面性考慮，下面是無交點(diǎn)情況下經(jīng)過斷開處理后的示意圖：無交點(diǎn)情況1斷開后無交點(diǎn)情況2斷開后最后給出有環(huán)情況下的求鏈表交點(diǎn)的算法，注意該算法的前提是鏈表有環(huán)：Node*FindCrossingNodeLoopNode*L1,Node*L2int nCircleLen1；Node*Start1=FindCircleStartL1,nCircleLen1；Node*Last1=NULL；Node*cNode=NULL；/crossing node ifNULL=Start1/L1中不存在環(huán)，結(jié)合前提，L2中必存在環(huán)，那么L1和L2肯定不相交，參考無交點(diǎn)情況1return NULL；elseLast1=KthNodeStart1,nCircleLen1；/找到環(huán)的末節(jié)點(diǎn)，這是前面的一個(gè)小算法Last1-next=NULL；/斷開L1中的環(huán)/執(zhí)行到這里時(shí)，說明L1中存在環(huán)，并且已經(jīng)被斷開了int nCircleLen2；Node*Start2=FindCircleStartL2,nCircleLen2；Node*Last2=NULL；if