微软等数据结构与算法面试100题 第七题
第七题
微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。
问题扩展：
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?
实现代码：
[cpp]
#include<iostream>
using namespace std;
struct linkNode
{
linkNode * nextLinkNode;
float value;
};
bool check2LinkList(linkNode * head1, linkNode * head2)
{
bool boolRingList1 = false;
bool boolRingList2 = false;
bool boolMutual = false;
//判断是否存在环
linkNode * tempLinkNode1 = head1;
linkNode * tempLinkNode2 = head1;
while(NULL!=tempLinkNode2)
{
tempLinkNode1 = tempLinkNode1->nextLinkNode;
tempLinkNode2 = tempLinkNode2->nextLinkNode;
if(NULL!=tempLinkNode2&&NULL!=tempLinkNode2->nextLinkNode)tempLinkNode2 = tempLinkNode2 ->nextLinkNode;
if(tempLinkNode1==tempLinkNode2)
{
boolRingList1 = true;
break;
}
}
tempLinkNode1 = head2;
tempLinkNode2 = head2;
while(NULL!=tempLinkNode2->nextLinkNode)
{
tempLinkNode1 = tempLinkNode1->nextLinkNode;
tempLinkNode2 = tempLinkNode2->nextLinkNode;
if(NULL!=tempLinkNode2&&NULL!=tempLinkNode2->nextLinkNode)tempLinkNode2 = tempLinkNode2 ->nextLinkNode;
if(tempLinkNode1==tempLinkNode2)
{
boolRingList2 = true;
break;
}
}
if(boolRingList1&&boolRingList2)
{
//都存在环
//cout<<"both have ring"<<endl;
int nodeMaxNum = 100;
int testStart = 0;
tempLinkNode1 = head1;
tempLinkNode2 = head2;
while(testStart<nodeMaxNum)
{
tempLinkNode1 = tempLinkNode1 ->nextLinkNode;
tempLinkNode2 = tempLinkNode2 ->nextLinkNode->nextLinkNode;
if(tempLinkNode1==tempLinkNode2)
{
boolMutual = true;
cout<<"存在环，有交点"<<endl;
break;
}
}
}
else if(boolRingList1||boolRingList2)
{
//一个存在环 一个不存在环
cout<<"一个存在环，木有交点"<<endl;
}
else
{
//不存在环 终点相同
tempLinkNode1 = head1;
tempLinkNode2 = head2;
while(NULL!=tempLinkNode1->nextLinkNode)
tempLinkNode1 = tempLinkNode1 ->nextLinkNode;
while(NULL!=tempLinkNode2->nextLinkNode)
tempLinkNode2 = tempLinkNode2 ->nextLinkNode;
if(tempLinkNode1==tempLinkNode2)
{
boolMutual = true;
cout<<"不存在环，有交点"<<endl;
}
}
return boolMutual;
}
int main()
{
#pragma region //构建测试链表 head1 head2 head3 head4 head5
// head1 与 head2 都不存在环 但存在相交
// head3 与 head4 存在环 存在相交
// head3 与 head1: head3存在环 head1 不存在环 不相交
// head3 与 head5: head3存在环
//
//
linkNode *head1 = new struct linkNode();
linkNode *b = new struct linkNode();
linkNode *c = new struct linkNode();
linkNode *d = new struct linkNode();
linkNode *e = new struct linkNode();
head1->nextLinkNode = b;
head1->value = 0;
b->nextLinkNode = c;
b->value = 1;
c->nextLinkNode = d;
c->value = 2;
d->nextLinkNode = e;
d->value = 3;
e->nextLinkNode = NULL;
e->value = 4;
补充：软件开发 , C++ ,
