求兩個(gè)鏈表是否有交點(diǎn)和交點(diǎn)位置油猫。
先判斷是否有環(huán)。如果兩者一個(gè)有一個(gè)沒(méi)有柠偶，一定沒(méi)有交點(diǎn)情妖。
兩者無(wú)環(huán)
思路很簡(jiǎn)單：先求兩者長(zhǎng)度，然后較大者先從頭指針出走m步诱担，m是兩者長(zhǎng)度差值毡证。然后兩指針同時(shí)開(kāi)始走，如果兩者有交蔫仙，則兩指針一定會(huì)在某一點(diǎn)相遇料睛。如果不是，則兩指針在都為空之前均不相等。
CODE
bool chkIntersect(ListNode* headA, ListNode* headB) {
if(!headA || !headB)
return false;
int len1=ListLen(headA);
int len2=ListLen(headB);
if(len1>len2){
for(int i=0;i<len1-len2;i++){
headA=headA->next;
}
}else{
for(int i=0;i<len2-len1;i++){
headB=headB->next;
}
}
while(headA){
if(headA==headB)
return true;
headA=headA->next;
headB=headB->next;
}
return false;
}
兩者有環(huán)
如果兩者有環(huán)秦效，那么交點(diǎn)可能在入環(huán)前雏蛮，或入環(huán)后涎嚼。
-
找到兩者入環(huán)結(jié)點(diǎn)阱州，如果相等，則交點(diǎn)在入環(huán)前法梯。使用“兩者無(wú)環(huán)”情況的思路苔货，以入環(huán)結(jié)點(diǎn)為尾結(jié)點(diǎn)，求出兩鏈表長(zhǎng)度立哑，然后錯(cuò)位遍歷夜惭。
-
如果兩入環(huán)結(jié)點(diǎn)不相等：
這種情況下，可能是無(wú)交铛绰，或者交點(diǎn)在環(huán)內(nèi)诈茧。方法是其中一個(gè)入環(huán)結(jié)點(diǎn)（比如node2）沿著所在環(huán)遍歷一遍回到原來(lái)位置，如果node1也在環(huán)內(nèi)捂掰，兩者就會(huì)相遇敢会。反之，兩者就是無(wú)交这嚣。
CODE
函數(shù)1：判斷是否有環(huán)鸥昏，返回入環(huán)結(jié)點(diǎn)
ListNode* chkLoop(ListNode* head) {
if(!head || !head->next)
return nullptr;
ListNode* H=new ListNode(0);
H->next=head;
ListNode *fast=H,*slow=H;
while(fast->next && fast->next->next){
fast=fast->next->next;
slow=slow->next;
if(fast==slow){
break;
}
}
if(fast!=slow)
return nullptr;
slow=H;
while(fast!=slow){
fast=fast->next;
slow=slow->next;
}
delete H;
return fast;
}
函數(shù)2：求鏈表的長(zhǎng)度，截止于參數(shù)2之前的位置
int ListLen(ListNode* h,ListNode* tnext){
int len=0;
while(h!=tnext){
len++;
h=h->next;
}
return len;
}
這樣的話姐帚，當(dāng)tnext==NULL時(shí)就是求整個(gè)鏈表的長(zhǎng)度吏垮。
函數(shù)3：已知兩個(gè)鏈表均以tnext做尾后，求是否相交
ListNode* rLinkJoint(ListNode* headA, ListNode* headB,ListNode* tnext) {
if(!headA || !headB)
return nullptr;
int len1=ListLen(headA,tnext);
int len2=ListLen(headB,tnext);
if(len1>len2){
for(int i=0;i<len1-len2;i++){
headA=headA->next;
}
}else{
for(int i=0;i<len2-len1;i++){
headB=headB->next;
}
}
while(headA!=tnext){
if(headA==headB)
return headA;
headA=headA->next;
headB=headB->next;
}
return nullptr;
}
這樣的話罐旗，當(dāng)tnext==NULL時(shí)就是正常無(wú)環(huán)鏈表的情況膳汪。
函數(shù)4：判斷情況以及交點(diǎn)在入環(huán)部分的代碼
bool chkInter(ListNode* head1, ListNode* head2, int adjust0, int adjust1) {
ListNode *join1=chkLoop(head1),*join2=chkLoop(head2);
if(!join1 && !join2){
return rLinkJoint(head1, head2,nullptr);
}else if(join1 && join2){
if(join1==join2){
return rLinkJoint(head1, head2,join1->next);
}else{
ListNode *p=join1;
do{
if(p==join2)
return true;
p=p->next;
}while(p!=join1);
return false;
}
}else
return false;
}
思考
鏈表以NULL做尾后，我們也可以自己知道尾后參數(shù)九秀，來(lái)增加函數(shù)的
