题目链接

解题思路

PAT的经典题，建议多做几遍，反正我做这种题，做了不下五遍了。

#include<bits/stdc++.h>
using namespace std;
struct node{
	int pre1,pre2,next,add;
	char c;
}E[100005];
int main(){
	int p1,p2,n,add;
	while(cin>>p1>>p2>>n){
		for(int i=0;i<n;i++){
			cin>>add;
			E[add].add=add;
			cin>>E[add].c>>E[add].next;
		}
		
		int pre1=-2;
		while(p1 !=-1){   //记录前一个节点 
			E[p1].pre1 = pre1;
			pre1 = p1;
			p1 = E[p1].next;
		}
		int pre2=-2;
		while(p2 !=-1){  //记录前一个节点 
			E[p2].pre2 = pre2;
			pre2 = p2;
			p2 = E[p2].next;
		}
		
		while(pre2!=-2 &&pre1 != -2){ //从尾往前查 
			if(E[pre1].c == E[pre2].c){
				pre1 = E[pre1].pre1;
				pre2 = E[pre2].pre2;
			}else 
				break;
		}
		if(pre1==-2&&pre2==-2) cout<<-1<<endl; 
		else cout<< E[pre1].next<<endl;
	}
	
	
	return 0;
}