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

1、兩個鏈表相交以及第一個公共節(jié)點(diǎn)的問題判讀兩個鏈表是否相交以及如果相交它們的第一個公共節(jié)點(diǎn)的問題，主要分這么幾種情況：1 ）兩個鏈表均不含有環(huán)2 ）兩個鏈表均含有環(huán)對于一個有環(huán)一個沒有，那么它們即不相交也沒有公共節(jié)點(diǎn)首先定義節(jié)點(diǎn)的結(jié)構(gòu)1struct Node23int value;4Node *next;5;判斷鏈表是否有環(huán)函數(shù)1boolisRingList(Node *head)23if(NULL =head)4returnfalse;5Node *p1 =head, *p2 = p1->next;6while(p2 !=NULL && p2->next!=NULL

2、)78p1 =p1->next;9p2 =p2->next->next;10if(p1= p2)11return true;1213return false;141 ）兩個鏈表均不含有環(huán)1.1 ）判斷兩個鏈表是否相交對于不含有環(huán)的兩個鏈表只要判斷它們的 tail 是否相等就可以決定它們是否相交1bool isCnnNonRingList(Node *h1, Node *h2)23Node *p1, *p2;4while(h1 != NULL)56p1 = h1;7h1 = h1->next;89while(h2 != NULL)1011p2 = h2;12h2 = h2

3、->next;131415return (p1 = p2);161.2） 找到它們的第一個公共節(jié)點(diǎn)對于不含有環(huán)的連個鏈表，只要從頭開始縮短長度較長的鏈表的長度知道長度相等，然后 同時移動兩個鏈表，第一個相同節(jié)點(diǎn)即為交點(diǎn)1Node* findFirstComNonRingList(Node *h1, Node *h2)23if(!isCnnNonRingList(h1, h2)4return NULL;5Node *p1 = h1, *p2 = h2;6int len1 = NonRingListLen(h1);7int len2 = NonRingListLen(h2);8if(len1

4、 < len2)910p1 = h2;11p2 = h1;12len1 = len1 + len2;13len2 = len1 - len2;14len1 = len1 - len2;1516while(len1 > len2)1718p1 = p1->next;19len1-;2021while(p1!=p2 && len1!=0)2223p1 = p1->next;24p2 = p2->next;2526return p1;272 ）對于兩個鏈表均還有環(huán)的情況這個問題比較復(fù)雜了 - - ，為了簡單，我還是先給出求它們公共節(jié)點(diǎn)的算法，2.1 ）兩

5、個含有環(huán)的鏈表的公共節(jié)點(diǎn)主要思路是，分別求出，兩個含有環(huán)鏈表的環(huán)的入口節(jié)點(diǎn)，如果他們相等則以它們的入口節(jié)點(diǎn)為 tail 分別計算兩個鏈表的長度，然后就和無環(huán)鏈表的情況一樣了。1/ 找到帶環(huán)鏈表入口節(jié)點(diǎn)函數(shù)2Node* findEnterRing(Node *head)34/ 判斷， head 是否帶環(huán)也不做了 :)5/ 這里面涉及到一個運(yùn)算6/ 從開始， p1 每次走一步， p2 每次走兩步，環(huán)的長度 r ，7/ 第一次相遇時， 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)到第一次相遇點(diǎn)距離

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

7、ingList(Node *h1, Node *h2)3435/ 為了簡單，判斷 h1,h2 是否有環(huán)就不做了吧 :)36Node *p1 = findEnterRing(h1);37Node *p2 = findEnterRing(h2);38if(p1 != p2)39return NULL;40int len1 = 1, len2 =1;414243444546474849505152535455565758596061626364656667686970717273747576Node *l1 = h1; while(l1!=p1) len1+; l1= l1->next;Nod

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