兩個(gè)鏈表相交以及第一個(gè)公共節(jié)點(diǎn)的問(wèn)題

1、學(xué)而不思則惘，思而不學(xué)則殆1234567891011121314345678兩個(gè)鏈表相交以及第一個(gè)公共節(jié)點(diǎn)的問(wèn)題判讀兩個(gè)鏈表是否相交以及如果相交它們的第一個(gè)公共節(jié)點(diǎn)的問(wèn)題，主要分這么幾種情況:1）兩個(gè)鏈表均不含有環(huán)2）兩個(gè)鏈表均含有環(huán)對(duì)于一個(gè)有環(huán)一個(gè)沒(méi)有，那么它們即不相交也沒(méi)有公共節(jié)點(diǎn)首先定義節(jié)點(diǎn)的結(jié)構(gòu)1 struct Node2 3 intvalue;4 Node*next;5 ;判斷鏈表是否有環(huán)函數(shù)bool isRingList(Node *head)if(NULL = head)return false;Node *p1 = head, *p2 = p1->next;while(p

2、2 != NULL && p2->next!=NULL) p1 = p1->next;p2 = p2->next->next;if(p1 = p2) return true;return false;1）兩個(gè)鏈表均不含有環(huán)1.1）判斷兩個(gè)鏈表是否相交對(duì)于不含有環(huán)的兩個(gè)鏈表只要判斷它們的tail是否相等就可以決定它們是否相交bool isCnnNonRingList(Node *h1, Node *h2) Node *p1, *p2; while(h1 != NULL) p1 = h1;h1 = h1->next; 910111213141516wh

3、ile(h2 != NULL)p2 = h2;h2 = h2->next;return (p1 = p2);1.2）找到它們的第一個(gè)公共節(jié)點(diǎn)對(duì)于不含有環(huán)的連個(gè)鏈表，只要從頭開(kāi)始縮短長(zhǎng)度較長(zhǎng)的鏈表的長(zhǎng)度知道長(zhǎng)度相等，然后 同時(shí)移動(dòng)兩個(gè)鏈表，第一個(gè)相同節(jié)點(diǎn)即為交點(diǎn)123456789101112131415161718192021222324252627Node* findFirstComNonRingList(Node *h1, Node *h2) if(!isCnnNonRingList(h1, h2) return NULL;Node *p1 = h1, *p2 = h2;intlen1

4、 = NonRingListLen(h1);intlen2 = NonRingListLen(h2);if(len1 < len2)p1 = h2;p2 = h1;len1 = len1 + len2;len2 = len1 - len2;len1 = len1 - len2;while(len1 > len2) p1 = p1->next; len1-; while(p1!=p2 && len1!=0)p1 = p1->next;p2 = p2->next;return p1;2）對(duì)于兩個(gè)鏈表均還有環(huán)的情況這個(gè)問(wèn)題比較復(fù)雜了 -,為了簡(jiǎn)單，我還是

5、先給出求它們公共節(jié)點(diǎn)的算法,2.1 ）兩個(gè)含有環(huán)的鏈表的公共節(jié)點(diǎn)主要思路是，分別求出，兩個(gè)含有環(huán)鏈表的環(huán)的入口節(jié)點(diǎn)，如果他們相等則以它們的入口 節(jié)點(diǎn)為tail分別計(jì)算兩個(gè)鏈表的長(zhǎng)度，然后就和無(wú)環(huán)鏈表的情況一樣了。1 /找到帶環(huán)鏈表入口節(jié)點(diǎn)函數(shù)2 Node* findEnterRing(Node *head)3 4 判斷，head是否帶環(huán)也不做了 :)5 /這里面涉及到一個(gè)運(yùn)算6 從開(kāi)始，pl每次走一步，p2每次走兩步，環(huán)的長(zhǎng)度r,7 /第一次相遇時(shí)，p1走了 s步，p2走了 2s步，則8 /2s = s+n*r ,其中n為p2在環(huán)內(nèi)循環(huán)的次數(shù)，那么，起始點(diǎn)到入口點(diǎn)距離為a,9 /入口點(diǎn)到第一次

6、相遇點(diǎn)距離為 x,則10 /a+x=s=n*r;11 /a=(n-1)*r+r-x;12 /通過(guò)這里看以看出，從起始點(diǎn)和相遇點(diǎn)，分別每次走一步，那么它們會(huì)在環(huán)的入口點(diǎn)相13遇14 那么，就有了如下求出環(huán)入口點(diǎn)的算法15 Node *p1 = head, *p2 = head;16 do17 18 p1 = p1->next;19 p2 = p2->next;20while(p1!=p2);21p2 = head;22while(p1!=p2)2324p1=p1->next;25p2=p2->next;2627returnp1;28 2930313233 Node *fi

7、ndFirstComRingList(Node *h1, Node *h2)34 35 為了簡(jiǎn)單，判斷h1,h2是否有環(huán)就不做了吧:)36Node *p1 = findEnterRing(h1);37Node *p2 = findEnterRing(h2);38if(p1 != p2)39return NULL;40int len1 = 1, len2 =1;414243444546474849505152535455565758596061626364656667686970717273747576Node *11 = h1; whi1e(11!=p1) 1en1+;11= l1->n

8、ext;Node *l2 = h2;while(l2!=p2)len2+;l2 = l2->next;11 = h1;12 = h2;if(len1 < len2) l1=h2;l2=h1;len1 = len1+len2; len2 = len1-len2; len1 = len1-len2;while(len1 > len2)l1 = l1->next; len1-;while(l1!=l2 && len1!=0) l1=l1->next; l2=l2->next; len1-;return l1;2.2）兩個(gè)帶環(huán)鏈表相交的問(wèn)題也分兩種情況吧情況1 :這里貼不了圖，可能是瀏覽器的問(wèn)題=就用簡(jiǎn)圖吧如果它們的它們的環(huán)的入口節(jié)點(diǎn)相同，那么可以，分別找到它們的環(huán)的入口節(jié)點(diǎn)判斷是否相等，如果相等則相交，不相等則不想交情況2:對(duì)于相交但是如果節(jié)點(diǎn)不相同的情況就像這樣headl:1->2->3->4->5->6->7->8->4;head2:9->8->4->5->6->7->8;具體圖像自己腦補(bǔ)吧：），這種情況，我能想到得是，先通過(guò)上面的方