PAT甲级1032.

目录

A1032

题目

样例

样例1

输入:

11111 22222 9
67890 i 00002
00010 a 12345
00003 g -1
12345 D 67890
00002 n 00003
22222 B 23456
11111 L 00001
23456 e 67890
00001 o 00010

输出:

67890

样例2

输入:

00001 00002 4
00001 a 10001
10001 s -1
00002 a 10002
10002 t -1

输出:

-1

思路和坑点

　　寻找两个链表的重合点。给节点多一个标记为，访问过标记为1，否则是0。第一个链表访问时候进行标记，第二个链表进行访问的时候如果遇到了已经访问过得，便是公共部分，或者没有公共结点，输出-1.

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef struct node{
    char data;
    int next,tag;
    node(){
        tag=0;
    }
}Node;
Node a[100000];
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int head1,head2,n;
    scanf("%d %d %d",&head1,&head2,&n);
    getchar();                                        //吸收换行符 
    for(int i=0;i<n;i++){
        int id;
        scanf("%d",&id);
        scanf(" %c %d",&a[id].data,&a[id].next);
        getchar();                                    //吸收换行符 
    }
    for(int i=head1;i!=-1;i=a[i].next)                //对第一个链表进行遍历，并作标记 
        a[i].tag=1;
    int i;
    for(i=head2;i!=-1;i=a[i].next){                    //遍历第二个链表，如果到了已标记处，说明是重合部分，否则到最后的-1 
        if(a[i].tag==1)
            break;
    }
    if(i==-1) printf("-1");
    else printf("%05d",i);
    return 0;
}