pat甲级 1032 Sharing

生僻词汇：suffix 后缀

题意：给出两条链表的首地址以及一共有多少个结点，然后给出每个结点的地址，数据，下一个结点的地址，求两个链表的首个共同结点的地址。如果不存在这个结点，就输出-1。

思路：先循环遍历第一个链表，把遍历到的链表结点都标记为1；

          遍历第二个链表，如果标记为1就说明这个结点第一个链表已经遍历过了，就输出然后跳出循环。

         循环完第二个链表都找不到，输出-1.

注意点：使用%05格式输出地址，高位补0；

              使用map会超时，应使用unordered_map;

　　　　scanf使用%c格式时是可以读入空格的，因此在输入地址，数据，下一个结点的地址时，格式不能写成%d%c%d，必须在中间加空格。

AC代码：

#include<iostream> 
#include<cstdio>
#include<vector>
#include<unordered_map>
using namespace std;
struct node{
    int s;
    char a;
    int next;
    int w;//是否读过的标记
};
int main(){
    unordered_map<int,node>mapp;
    int start1,start2,n;
    cin>>start1>>start2>>n;
    node x;
    while(n--){
        cin>>x.s>>x.a>>x.next;
        x.w=0;//将标记赋值为0
        mapp[x.s]=x;
    }
    int flag=0;
    int y=start1;
    while(y!=-1){
        mapp[y].w=1;
        y=mapp[y].next;
    }
    y=start2;
    while(y!=-1){
        if(mapp[y].w==1){
            flag=1;
            printf("%05d",y);
            break;
        }
        y=mapp[y].next;
    }
    if(!flag)cout<<-1;
}