PAT A1032 Sharing (25分)

前言

传送门

正文

参考题解

#include<iostream>
#include<algorithm>
using namespace std;
/* 题意：找到两条链表的第一个公共结点的位置 思路：由于地址范围较小，故考虑使用静态链表，找到两条链表的 第一个公共结点即可，可以在结构体中新增一个成员变量flag来表示是否 在第一条链表中出现过，然后在遍历第二条链表时就可以确定这个公共结点。 */
const int N=1e5+10;
struct Node{
	char data;
	int next;
	bool flag;//flag==false表示在第一条链表中未出现 
}node[N];
int main(){
	int a1,a2,n,addr,next;
	char data;
	cin>>a1>>a2>>n; 
	while(n--){
		scanf("%d %c %d",&addr,&data,&next);
		node[addr]={data,next,false};
	} 
	int p;
	for(p=a1;p!=-1;p=node[p].next){
		node[p].flag=true;
	}
	for(p=a2;p!=-1;p=node[p].next){
		if(node[p].flag)break;
	}
	if(p!=-1) printf("%05d\n",p);
	else printf("-1\n");
	return 0;
}