最开始没有理解题意,如果两个单词只有其中的某一个字母是相同的,这个字母之后又变得不同了怎么办?这个题其实暗含了一个条件,就是如果出现这样的情况,那么这个相同的字母会存在不同的地址中,因此如果两个单词中的某一个字母地址是相同的,那么就说明它们之后的所有字母都是相同的。
因此只需要设置一个数组a,遍历第一个单词链表的时候,把出现的每一个单词的地址在a中设为1,这样在遍历第二个链表的时候,如果那个字母的地址在a中是1,就表示它们此后的所有字母都是相同的。
#include<cstdio>
const int N=100010;
char e[N];
int ne[N];
bool a[N]; //表示某一个地址的结点是否出现过
int main(){
for(int i=0;i<N;i++){ //初始化a都为0
a[i]=0;
}
int n,head1,head2;
scanf("%d%d%d",&head1,&head2,&n);
for(int i=0;i<n;i++){
int add;
char data;
int next;
scanf("%d %c %d",&add,&data,&next); //注意char型变量在scanf的时候会吃空格
e[add]=data;
ne[add]=next;
}
for(int i=head1;i!=-1;i=ne[i]){
a[i]=1;
}
int j;
for(j=head2;j!=-1;j=ne[j]){
if(a[j]==1) //说明在此之后的字母都是相同的
break;
}
if(j!=-1)
printf("%05d",j);
else
printf("-1");
return 0;
}