左神基础班- 可能有环可能无环的链表 -判断是否相交
//判断是否有环
LinkNode* loop(LinkNode* head){
LinkNode* f = head->next;
LinkNode* s = head->next;
//注意这边的 &&
while(f->next != nullptr && f->next->next != nullptr){
s = s->next;
f = f->next->next;
if(s == f){
f = head->next;
break;
}
}
//代表无环
if(f->next==nullptr || f->next->next == nullptr){
return nullptr;
}
//若有环
while(s != f){
s = s->next;
f = f->next;
}
return s;
}
//2无环单链表是否相交
LinkNode* noloop(LinkNode* head1, LinkNode* head2){
int num1 = 0;
int num2 = 0;
LinkNode* go1 = head1;
LinkNode* go2 = head2;
while(go1->next != nullptr){
go1 = go1->next;
num1++;
}
while(go2->next != nullptr){
go2 = go2->next;
num2++;
}
if(go1 != go2){
return nullptr;
}
num1 = num1-num2;
go1 = num1 > 0? head1:head2;
go2 = go1 == head1? head2 : head1;
if(num1<0){
num1 = -num1;
}
while(num1 > 0){
go1 = go1->next;
num1--;
}
while(go1 != go2){
go1 = go1->next;
go2 = go2->next;
}
return go1;
}
//两个有环链表 是否相交
LinkNode* hasloop(LinkNode* head1, LinkNode* head2){
//在环外的链上相交,则其入环节点一定相同
if(loop(head1) == loop(head2)){
LinkNode* enloop = loop(head1);
LinkNode* go1 = head1;
LinkNode* go2 = head2;
int num1 = 0;
int num2 = 0;
while(go1 ->next != enloop){
num1++;
go1 = go1->next;
}
while(go2->next != enloop){
num2++;
go2 = go2->next;
}
num1 = num1 - num2;
go1 = num1 > 0? head1 : head2;
go2 = go1 == head1 ? head2 : head1;
if(num1<0)
num1 = -num1;
while(num1 > 0){
go1 = go1->next;
num1--;
}
while(go1 != go2){
go1 = go1->next;
go2 = go2->next;
}
return go1;
}else{
//另外两种结构: 66 或 三毛头没有中间一根毛
//从一个入环节点开始沿着环遍历,如果重新回到原始位置没碰到另外一个入环节点,则为66结构
LinkNode* enloop1 = loop(head1);
LinkNode* enloop1_go = enloop1;
LinkNode* enloop2 = loop(head2);
while(enloop1_go->next != enloop1){
enloop1_go = enloop1_go->next;
if(enloop1_go == enloop2){
return enloop1;
}
}
//66结构
return nullptr;
}
}
最终组合起来使用: return nullptr; 表示 一个有环一个无环的链表比不相交
LinkNode* judge(LinkNode* head1, LinkNode* head2){
if(head1 == nullptr || head2 == nullptr){
return nullptr;
}
// 两个无环单链表是否相交
if(loop(head1) == nullptr && loop(head2) == nullptr){
return noloop(head1, head2);
}else if(loop(head1) != nullptr && loop(head2)!= nullptr){
return hasloop(head1, head2);
}
return nullptr;
}
完整的 ,带测试的代码:
//拷贝带有随机指针的单链表
#include<iostream>
#include<stack>
#include<unordered_map>
using namespace std;
struct LinkNode{
int value;
LinkNode* next;
LinkNode(int a){
value = a;
next = nullptr;
}
};
LinkNode* loop(LinkNode* head);
LinkNode* noloop(LinkNode* head1, LinkNode* head2);
LinkNode* hasloop(LinkNode* head1, LinkNode* head2);
LinkNode* judge(LinkNode* head1, LinkNode* head2);
int main(){
LinkNode* head1 = new LinkNode(0);
LinkNode* a = new LinkNode(1);
LinkNode* b = new LinkNode(2);
LinkNode* c = new LinkNode(3);
LinkNode* d = new LinkNode(4);
head1->next = a;
a->next = b;
b->next = c;
c->next = d;
//加环
d->next = b;
LinkNode* head2 = new LinkNode(0);
LinkNode* a2 = new LinkNode(1);
LinkNode* b2 = new LinkNode(2);
LinkNode* c2 = new LinkNode(3);
LinkNode* d2 = new LinkNode(4);
head2->next = a2;
a2->next = b2;
b2->next = c2;
c2->next = d2;
d2->next = b2;
// b2->next = c2;
//判断一个单链表是否有环
// if(loop(head2)){
// cout << loop(head)->value <<endl;
// }else{
// cout << "无环" << endl;
// }
// 测试 66 结构
if(judge(head1, head2) == nullptr){
cout << "66"<< endl;
}
LinkNode* head3 = new LinkNode(0);
LinkNode* a3 = new LinkNode(1);
LinkNode* b3 = new LinkNode(2);
LinkNode* c3 = new LinkNode(3);
LinkNode* d3 = new LinkNode(4);
LinkNode* e3 = new LinkNode(5);
head3->next = a3;
a3->next = b3;
b3->next = c3;
c3->next = d3;
d3->next = e3;
e3->next = c3;
LinkNode* head4 = new LinkNode(0);
LinkNode* a4 = new LinkNode(1);
head4->next = a4;
a4->next = b3;
//测试环外相遇结构
if(judge(head3,head4) != nullptr){
cout << "seconde mode: the node is "<<judge(head3, head4)->value << endl;
}
LinkNode* head5 = new LinkNode(0);
LinkNode* a5 = new LinkNode(1);
head5->next = a5;
a5->next = d3;
//环内相交节点
if(judge(head3,head5) != nullptr){
cout <<"third mode: the node is"<< judge(head3, head5)->value << endl;
}
LinkNode* head6 = new LinkNode(0);
LinkNode* a6 = new LinkNode(1);
LinkNode* b6 = new LinkNode(2);
LinkNode* c6 = new LinkNode(3);
LinkNode* d6 = new LinkNode(4);
LinkNode* e6= new LinkNode(5);
head6->next = a6;
a6->next = b6;
b6->next = c6;
c6->next = d6;
d6->next = e6;
LinkNode* head7 = new LinkNode(0);
LinkNode* a7 = new LinkNode(1);
LinkNode* b7 = new LinkNode(2);
head7->next = a7;
a7->next = b7;
b7->next = c6;
//两单链表相交
if(judge(head6,head7) != nullptr){
cout <<"two Link have banana, the number : "<< judge(head6, head7)->value;
}else{
cout << "two Link no banana" <<endl;
}
return 0;
}
//判断是否有环
LinkNode* loop(LinkNode* head){
LinkNode* f = head->next;
LinkNode* s = head->next;
//注意这边的 &&
while(f->next != nullptr && f->next->next != nullptr){
s = s->next;
f = f->next->next;
if(s == f){
f = head->next;
break;
}
}
//代表无环
if(f->next==nullptr || f->next->next == nullptr){
return nullptr;
}
//若有环
while(s != f){
s = s->next;
f = f->next;
}
return s;
}
//2无环单链表是否相交
LinkNode* noloop(LinkNode* head1, LinkNode* head2){
int num1 = 0;
int num2 = 0;
LinkNode* go1 = head1;
LinkNode* go2 = head2;
while(go1->next != nullptr){
go1 = go1->next;
num1++;
}
while(go2->next != nullptr){
go2 = go2->next;
num2++;
}
if(go1 != go2){
return nullptr;
}
num1 = num1-num2;
go1 = num1 > 0? head1:head2;
go2 = go1 == head1? head2 : head1;
if(num1<0){
num1 = -num1;
}
while(num1 > 0){
go1 = go1->next;
num1--;
}
while(go1 != go2){
go1 = go1->next;
go2 = go2->next;
}
return go1;
}
//两个有环链表 是否相交
LinkNode* hasloop(LinkNode* head1, LinkNode* head2){
//在环外的链上相交,则其入环节点一定相同
if(loop(head1) == loop(head2)){
LinkNode* enloop = loop(head1);
LinkNode* go1 = head1;
LinkNode* go2 = head2;
int num1 = 0;
int num2 = 0;
while(go1 ->next != enloop){
num1++;
go1 = go1->next;
}
while(go2->next != enloop){
num2++;
go2 = go2->next;
}
num1 = num1 - num2;
go1 = num1 > 0? head1 : head2;
go2 = go1 == head1 ? head2 : head1;
if(num1<0)
num1 = -num1;
while(num1 > 0){
go1 = go1->next;
num1--;
}
while(go1 != go2){
go1 = go1->next;
go2 = go2->next;
}
return go1;
}else{
//另外两种结构: 66 或 三毛头没有中间一根毛
//从一个入环节点开始沿着环遍历,如果重新回到原始位置没碰到另外一个入环节点,则为66结构
LinkNode* enloop1 = loop(head1);
LinkNode* enloop1_go = enloop1;
LinkNode* enloop2 = loop(head2);
while(enloop1_go->next != enloop1){
enloop1_go = enloop1_go->next;
if(enloop1_go == enloop2){
return enloop1;
}
}
//66结构
return nullptr;
}
}
LinkNode* judge(LinkNode* head1, LinkNode* head2){
if(head1 == nullptr || head2 == nullptr){
return nullptr;
}
// 两个无环单链表是否相交
if(loop(head1) == nullptr && loop(head2) == nullptr){
return noloop(head1, head2);
}else if(loop(head1) != nullptr && loop(head2)!= nullptr){
return hasloop(head1, head2);
}
return nullptr;
}
ok,88~~