首页 > 代码库 > 单链表是否相交

单链表是否相交

2024-11-02 00:38:02   206人阅读

题目：有两个带头结点的单链表L1,L2,判断它们是否相交（它们中是否有相同的结点）

解题思路：
L1，L2中任何一个链表为空它们不相交
因为单链表中可能有环，所以分3种情况讨论
1、L1,L2中都没有环，那么可以通过判断它们中最后一个结点是否相同，来判断它们是否相交
2、L1,L2中一个有环，一个没有环，那么它们一定不相交
3、L1,L2中都有环，那么只有当它们的环相同时，它们才相交，当它们在进入环之前有相同的结点时，它们交点的个数大于环中结点的个数，当它们进入环时才有第一个相同的结点时，它们交点的个数等于于环中结点的个数，这两种情况下，都可以通过判断它们环的入口结点是否相同来判断它们是否相交。


ADT定义如下
#define ElemType char
typedef struct LNode{
    ElemType data;
    LNode *next;
}LNode,*LinkList;


算法实现：
bool isIntersect(LinkList &L1,LinkList &L2)
{
if(L1==NULL||L2==NULL) return false;//L1，L2中任何一个链表为空它们不相交


//L1,L2中都没有环
if(!(hasCircle(L1)||hasCircle(L2)))
{
LNode* p=L1;
LNode* q=L2;
while(p->next)
{
p=p->next;
}
while(q->next)
{
q=q->next;
}
if(p==q) return true;//两个无环单链表，最后一个结点相同时，它们相交
return false;
}
//L1,L2中都有环
else if(hasCircle(L1)&&hasCircle(L2))
{
if(searchEntranceNode(L1)== searchEntranceNode(L2)) return true;//两个有环单链表，它们环的入口结点相同时，它们相交
return false;
}
//L1,L2中一个有环，一个没有环
else
{
return false;//两个单链表，一个有环，一个无环，它们一定不相交
}
}


hasCircle()方法是用来判断单链表是否有环，searchEntranceNode()方法是用来找单链表中环的入口结点的

我的一篇博文有写出它们的具体实现：单链表是否相交


拓展：有两个带头结点的单链表L1,L2,判断它们是否相交，并求出首次相交的结点


解题思路：
当L1与L2相交时，若L1与L2中都没有环，那么求出两个单链表中结点个数之差的绝对值dCount，让结点个数多的单链表从头结点开始往下走dCount步，让结点个数少的单链表从头结点开始往后走，然后同时让两个单链表每次往后走一步，直到他们相等，那么这个结点就是首次相交的结点。若L1与L2中都有环，求出单链表L1与L2从头结点到环入口结点的结点总个数count，求出两者之差的绝对值，让count大的单链表从头结点开始往下走dCount步，让count大的的单链表从头结点开始往后走，然后同时让两个单链表每次往后走一步，直到他们相等，那么这个结点就是首次相交的结点。


算法实现：

LNode* searchFirstIntersectNode(LinkList &L1,LinkList &L2)
{
if(isIntersect(L1,L2)) return NULL;//单链表L1与L2不相交时，返回NULL
if(!hasCircle(L1)) //L1中没有环时，L1与L2中都没有环
{
int count1=1;//单链表L1中结点的个数，包括头结点
int count2=1;//单链表L2中结点的个数，包括头结点
LNode* p=L1;
LNode* q=L2;
while(p->next)
{
p=p->next;
count1++;
}
while(q->next)
{
q=q->next;
count2++;
}
if(count1>=count2)//单链表L1比单链表L2长或两者一样长时
{
int dCount=count1-count2;//单链表L1比单链表L2多出的结点的个数
p=L1;
q=L2;
while(dCount>0)
{
p=p->next;
}
while(p)
{
if(p==q) return p;
p=p->next;
q=q->next;
}


}
else
{
int dCount=count2-count1;//单链表L2比单链表L1多出的结点的个数
p=L1;
q=L2;
while(dCount>0)
{
q=q->next;
}
while(q)
{
if(p==q) return p;
p=p->next;
q=q->next;
}


}
}
else //L1有环时，此时L1与L2都有环
{
int count1=1;//单链表L1中从头结点到环的入口结点之间所有结点的个数，包括头结点与环的入口结点
int count2=1;//单链表L2中从头结点到环的入口结点之间所有结点的个数，包括头结点与环的入口结点
LNode* p=L1;
LNode* q=L2;
while(p!= searchEntranceNode(L1))
{
p=p->next;
count1++;
}
while(q!=searchEntranceNode(L2))
{
q=q->next;
count2++;
}
if(count1>=count2)//单链表L1比单链表L2从头结点到环的入口结点之间所有结点的个数长或两者一样长时
{
int dCount=count1-count2;//单链表L1比单链表L2从头结点到环的入口结点之间所有结点的个数多出的结点的个数
p=L1;
q=L2;
while(dCount>0)
{
p=p->next;
}
while(p)
{
if(p==q) return p;
p=p->next;
q=q->next;
}


}
else
{
int dCount=count2-count1;//单链表L2比单链表L1从头结点到环的入口结点之间所有结点的个数多出的结点的个数
p=L1;
q=L2;
while(dCount>0)
{
q=q->next;
}
while(q)
{
if(p==q) return p;
p=p->next;
q=q->next;
}


}
}
return NULL;
}

上面的程序分两种情况：L1与L2中都没有环时，求首次相交结点；L1与L2中都有环时，求首次相交结点。其实L1与L2中都有环时，求首次相交结点，可以类似的看成L1与L2中都没有环时，求首次相交结点。只需要令L1与L2环中入口结点的next为空，那么L1与L2就成了没有环的单链表了。

PS：此时searchFirstIntersectNode()方法中的参数不是引用类型，因为L1与L2中都有环，会将L1与L2都转变成没有环的单链表，这个过程会改变L1与L2，但是我们不希望这个改变对原始的L1和L2进行改变，所以参数没有用引用类型


LNode* searchFirstIntersectNode(LinkList L1,LinkList L2)
{
if(isIntersect(L1,L2)) return NULL;//单链表L1与L2不相交时，返回NULL
if(hasCircle(L1)) searchEntranceNode(L1)->next=NULL;//令L1中环入口结点的next为NULL

int count1=1;//单链表L1中结点的个数，包括头结点
int count2=1;//单链表L2中结点的个数，包括头结点
LNode* p=L1;
LNode* q=L2;
while(p->next)
{
p=p->next;
count1++;
}
while(q->next)
{
q=q->next;
count2++;
}
if(count1>=count2)//单链表L1比单链表L2长或两者一样长时
{
int dCount=count1-count2;//单链表L1比单链表L2多出的结点的个数
p=L1;
q=L2;
while(dCount>0)
{
p=p->next;
}
while(p)
{
if(p==q) return p;
p=p->next;
q=q->next;
}


}
else
{
int dCount=count2-count1;//单链表L2比单链表L1多出的结点的个数
p=L1;
q=L2;
while(dCount>0)
{
q=q->next;
}
while(q)
{
if(p==q) return p;
p=p->next;
q=q->next;
}
}
return NULL;
}

单链表是否相交


联系
我们