两个链表相交以及第一个公共节点的问题

1、学而不思则惘，思而不学则殆1234567891011121314345678两个链表相交以及第一个公共节点的问题判读两个链表是否相交以及如果相交它们的第一个公共节点的问题，主要分这么几种情况:1）两个链表均不含有环2）两个链表均含有环对于一个有环一个没有，那么它们即不相交也没有公共节点首先定义节点的结构1 struct Node2 3 intvalue;4 Node*next;5 ;判断链表是否有环函数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）两个链表均不含有环1.1）判断两个链表是否相交对于不含有环的两个链表只要判断它们的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）找到它们的第一个公共节点对于不含有环的连个链表，只要从头开始缩短长度较长的链表的长度知道长度相等，然后 同时移动两个链表，第一个相同节点即为交点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）对于两个链表均还有环的情况这个问题比较复杂了 -,为了简单，我还是

5、先给出求它们公共节点的算法,2.1 ）两个含有环的链表的公共节点主要思路是，分别求出，两个含有环链表的环的入口节点，如果他们相等则以它们的入口 节点为tail分别计算两个链表的长度，然后就和无环链表的情况一样了。1 /找到带环链表入口节点函数2 Node* findEnterRing(Node *head)3 4 判断，head是否带环也不做了 :)5 /这里面涉及到一个运算6 从开始，pl每次走一步，p2每次走两步，环的长度r,7 /第一次相遇时，p1走了 s步，p2走了 2s步，则8 /2s = s+n*r ,其中n为p2在环内循环的次数，那么，起始点到入口点距离为a,9 /入口点到第一次

6、相遇点距离为 x,则10 /a+x=s=n*r;11 /a=(n-1)*r+r-x;12 /通过这里看以看出，从起始点和相遇点，分别每次走一步，那么它们会在环的入口点相13遇14 那么，就有了如下求出环入口点的算法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 为了简单，判断h1,h2是否有环就不做了吧:)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）两个带环链表相交的问题也分两种情况吧情况1 :这里贴不了图，可能是浏览器的问题=就用简图吧如果它们的它们的环的入口节点相同，那么可以，分别找到它们的环的入口节点判断是否相等，如果相等则相交，不相等则不想交情况2:对于相交但是如果节点不相同的情况就像这样headl:1->2->3->4->5->6->7->8->4;head2:9->8->4->5->6->7->8;具体图像自己脑补吧：），这种情况，我能想到得是，先通过上面的方