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

1、.轉(zhuǎn)載 常見和鏈表相關(guān)的算法原文地址：常見和鏈表相關(guān)的算法 daniel一、鏈表排序鏈表排序和數(shù)組排序的思路類似，只是鏈表操作起來比較費事，因為不能隨機訪問，所以只能借助于類似于前置或后置插入，添加等概念來完成。下面給出了鏈表排序的幾種方法。輔助代碼：/單鏈表節(jié)點的定義typedef struct LinkNodeint val；struct LinkNode*next；LinkNode；/由一個數(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.插入排序以從小到大排序為例鏈表排序最容易想到的是插入排序，它的根本想法是從第

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

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

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

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

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

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

9、L；/設置結(jié)果鏈表的完畢標記return L.next；注意上面if語句中的和=判斷，他們能使得鏈表的選擇排序是穩(wěn)定的排序。3.冒泡排序以從小到大排序為例鏈表的冒泡排序不太好想，主要是不太好控制比較邊界。這里我們用一個標記指針end表示邊界，每完成一趟冒泡后，end會被向前移一下，直到完成N-1趟冒泡。冒泡需要比較并交換相鄰的節(jié)點，因此我們在實現(xiàn)中使用了pre，cur，n等指針分別表示當前處理節(jié)點的前驅(qū)，當前處理節(jié)點和下一節(jié)點。鏈表冒泡排序的實現(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；/這里單獨處理頭結(jié)點和第二個節(jié)點的比較，這是沒有啞頭節(jié)點的鏈表的一個優(yōu)勢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.快速排序從小到大排序知道鏈表還可以快速排序是在筆試某公司時才發(fā)現(xiàn)的，當時只看到了個QsortList什么的，而且是個填空題，當時沒有思路，也沒有做出來，只記得那個QsortList帶了3個參數(shù)，還返回了個鏈接點指針?；貋砗蠹毾肓艘魂嚕l(fā)現(xiàn)原理和數(shù)組的快速排序是一樣的，只是鏈表在處理指針時比較費事，而且要保證排序后鏈表還是有序地鏈接在一起，不能出現(xiàn)掉鏈等情況，有些繞人。思路這樣，從鏈表中選取一個節(jié)點一般簡單地取頭結(jié)

12、點，將其值作為pivot，將鏈表中剩余的節(jié)點分成兩個子鏈表，其中一個中的所有值都小于pivot，另一個中的所有值都不小于pivot，然后將這兩條鏈表分別鏈接到pivot節(jié)點的兩端。然后對于子鏈表分別進展遞歸該過程，直到子鏈表中只有一個節(jié)點為止。下面給出了鏈表快速排序的一種實現(xiàn)方法，該實現(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，因為head還可能被子調(diào)用修改/同樣這里傳入pivot-next而非head2，這樣才能保證最后鏈表是有序鏈在一起的QsortListpivot-next,end；調(diào)用QsortList時采用這樣的方式QsortListL,NULL；數(shù)組的快速排序是不穩(wěn)定的，原因是其實現(xiàn)時采用了交換的機制；而鏈表的快速排序那么是穩(wěn)定的，其原因是，被掃描的節(jié)點是有序地依次添加到子鏈表的末尾，保證了兩個等值節(jié)點的相對位置不變。二、關(guān)于鏈表的其他筆試面試題很多公司都考這個東西，其實考來考去本質(zhì)就是那幾道題，比較根底的東西

15、，弄懂了其他類似的略微變一下就行了。1.單鏈表倒置就是倒插法了，假想如今有一個空鏈表這是鏈表的一個很好的優(yōu)點，定義一個指針，你就可以聲稱創(chuàng)立了一個鏈表了，很節(jié)省空間，對輸入的鏈表，從頭到尾進展掃描，把每個節(jié)點都插入到假想鏈表的頭部，然后返回假想的鏈表就可以，唯一需要注意的就是，邊界情況和完畢標記的NULL指針。下面是一種實現(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)于單鏈表的倒置，還有個遞歸的算法，雖然該算法在實際工作中沒有任何作用，除了應付某些考試或僅僅作為一種談資之外當然，也可以說是在啟發(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個節(jié)點，假設K大于鏈表長度那么返回NULL。這也是某公司的筆試題之一，出題者的意圖是不想讓做題者遍歷兩次鏈表，即你不能先數(shù)鏈表中到底有幾個節(jié)點。在不知道鏈表到底有幾個節(jié)點的前提

17、下找到倒數(shù)第K個節(jié)點，嗯，聽起來很酷，雖然可以先數(shù)數(shù)到底有多少個，做做減法，再去找順數(shù)第多少個實際上這個笨笨的方法和那個酷酷的方法進展的機器操作數(shù)的差異根本可以忽略，只是在鏈表非常長，而K值很小的情況下，笨方法需要再從頭來過，而酷方法可以每個節(jié)點過兩次，因此占到了部分性原理的廉價。說了這么多，還是看看實現(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個節(jié)點搞笑么?哪個公司會出這樣的題啊?呵呵，沒有公司會出這樣的題，我自己想的。只是為了下面可能用到，高手請?zhí)^。Node*KthNodeNode*head,int KifK=0return NULL；Node*p=head；whileNULL！=p&K 1p=p-next；K-；return p；4.不知道單鏈表節(jié)點前驅(qū)的情況下，刪除該節(jié)點被問到過這樣的問題，我笑而不

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

20、快的指針可以向前挪動兩步并且沒有到達鏈表的尾部的話，快指針就向前挪動2個節(jié)點，同時慢的指針向前挪動1個節(jié)點；否那么退出，返回慢指針。該算法的實現(xiàn)如下，注意區(qū)別鏈表長度為偶數(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ù)個節(jié)點時返回中間兩個節(jié)點的后一個。上面的算法中的循環(huán)需要略微調(diào)整

21、一下。前面的算法中，快指針p2每次都挪動2步，而本問題中，我們需要改變下策略，變成：只要快指針p2能向前挪動一步，那么快指針和慢指針就都同時向前挪動一步，再看看快指針是否還能補上一步，假設能補上一步，那么就補上，然后進展下一輪循環(huán)，否那么就表示到達了鏈表尾部，返回慢指針即可。實現(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；這種步長法的想法很巧妙，后面的題中還會使用。6.判斷單鏈表是否有環(huán)，并求出環(huán)開場的節(jié)點，參考1。假設沒有環(huán)，就返回NULL。如以以下圖中所示，該單鏈表環(huán)開場的節(jié)點是3。首先，我們判斷單鏈表是否有環(huán)，這里我們也借用了步長法，即指針p1，p2都指向鏈表頭，然后開場遍歷，p1每次挪動一步，p2每次挪動兩步，然后判斷p2有沒有遇到p1。假設遇到了p1，說明鏈表有環(huán)；假設遇到之前，p2就已經(jīng)到達鏈表尾部值為NULL，說明鏈表沒有環(huán)。判斷單鏈表是否有環(huán)算法的實現(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；如何證明這個算法的正確性?p2最多要繞環(huán)轉(zhuǎn)幾圈才能追上p1?關(guān)于這一點可以參考1中的證明，這里也再轉(zhuǎn)述下。上面的圖是鏈表有環(huán)時的示意圖，原作者沒有把它化成鏈表構(gòu)造，而只是以連續(xù)的線條代替，我們在考慮問題的時候需要注意到它們是離散的節(jié)點。下面就詳細分析該算法的思路：a.假設鏈表無環(huán)，我們的算法是能得到正確的結(jié)果的；b.這里我

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

25、算法是正確的。下面我們再來看看作者是怎樣求出環(huán)開場的節(jié)點A，順便計算出環(huán)的長度的。在前面的證明中，我們是從慢指針到達A點開場證明的，而忽略了前面從鏈表頭到A點的x個間隔 。如今假設慢指針從鏈表頭head到達A點時，快指針p2已經(jīng)挪動到了B點，設環(huán)長為s個節(jié)點，那么有關(guān)系式：2x=x+n*s+s-y。即x=n+1s y。當慢指針p1和快指針p2同時到達M點時，即到達前面證明的最后時，我們再增加下面一些操作：另起一個指針p從鏈表頭head開場挪動，每次挪動一個節(jié)點，同樣慢指針p1也繼續(xù)從M點向前挪動。當p經(jīng)過x步到達A時，p1也經(jīng)過n*s+s-y到達A點，和p相遇，這樣我們就找到了A點。在此過程中

26、，我們可以同時記下p1反復經(jīng)過M點的次數(shù)n，然后利用s=x+y/n+1計算環(huán)的長度。注意，我們無法直接單獨得到x或y的值，但卻能統(tǒng)計從head開場到慢指針p1和快指針p2第一次在M點相遇時經(jīng)過的循環(huán)次數(shù)x+y。下面的實現(xià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；/此時的p即為A點return NULL；另一種求環(huán)長的方法：當p1和p2第一次在M相遇時，我們已經(jīng)知道了鏈表是有環(huán)的了，所以還可以通過一種簡單的計數(shù)方法求環(huán)的長度，即用指針遍歷環(huán)一圈，直到重新回到M點。只是這樣，我們是無法得到環(huán)開場的節(jié)點A的。不難證明，以上算法的復雜度是線性的。下面給出一個引申的問題，該問題也是類似，可以在線性時間內(nèi)解決：假設一個單鏈表可能

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

29、不是同一個節(jié)點，假設是同一個節(jié)點，那么就兩鏈表就是相交的；假設是不同的兩節(jié)點，就是不相交的。求交點思路有些巧妙：在判斷是否存在交點遍歷兩鏈表的時候，我們可以順便分別計算兩鏈表的長度，然后計算其長度差d，再分別從短鏈表和長鏈表的第d個節(jié)點開場遍歷并判斷兩者是否相等，第一個相等的節(jié)點指針就是交點指針。實現(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)情況無交點情況1和無交點情況2分別顯示了一條及兩條鏈表有環(huán)時，不相交的情況，這兩種情況在設計算法時需要做一些考慮。無交點情況1無交點情況2有交點情況1顯示了環(huán)在交點后面的情況。有交點情況1有交點情況2顯示了交點是環(huán)開場的節(jié)點的情況。有交點情況2有交點情況3顯示了鏈表交點在環(huán)中間的情況。這種情況比較復雜，此時我們既可以認為交點是A節(jié)點，也可以認為交點是B節(jié)點。假設我們把環(huán)看成是L2的，那么就是L1交L2于A點；假設我們把環(huán)看成L1的，那么就是L2交L1于B點。實際上，這個環(huán)也是L1和L2共有的。因此此種情況下A和B都是鏈表的交點，我們只能通過間隔 遠

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

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

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