1.题目
https://pintia.cn/problem-sets/994805342720868352/problems/994805460652113920
静态链表，找出两条链表的首个公共结点。
2.思路
基础题。最巧妙点在于设一个int型变量flag，然后2次遍历——第一次遍历第一条链表（全部结点的flag改从false改为true），第二次遍历第二条链表，如果当前结点的flag是true则马上break跳出for循环（千万别忘了break！！），当然也可以直接return就好了。
注意点：
（1）用map容易超时；输出格式用%05d——不足5位的整数的高位补0；
（2）由于scanf使用%c格式时是可以读入空格的，所以读入当前地址、数据、后继地址时，scanf的格式不能写成%d%c%d，而要写成%d %c %d。
3.代码
#include<cstdio> #include<iostream> #include<stdlib.h> using namespace std; const int maxn=100010; struct Node{ char data; int next; bool flag;//结点是否在第一条链表中出现 }node[maxn]; int main(){ for(int i=0;i<maxn;i++) node[i].flag=false; int s1,s2,n; int address,next; scanf("%d%d%d",&s1,&s2,&n); char data;//数据 for(int i=0;i<n;i++){ scanf("%d %c %d",&address,&data,&next); node[address].data=data; node[address].next=next; } int p; for(p=s1;p!=-1;p=node[p].next){ node[p].flag=true;//枚举第一条链表的所有结点，令其出现次数为1 } for(p=s2;p!=-1;p=node[p].next){ //遍历第2链表，找到第一个已经在第一条链表中出现的结点 if(node[p].flag==true) break; } if(p!=-1){//如果第二条链表还没有到达结尾，说明找到了共用结点 printf("%05\n",p); }else{ printf("-1\n"); } system("pause"); }
4.模板总结
（1）定义静态链表。
（2）for循环对静态链表的每个结点的某元素初始化。
（3）遍历链表，计数：
int p=begin,count=0; while(p!=-1){//-1代表链表结束 XXX=1; count++; p=node[p]->next; }
（4）很多时候题目给出的结点并不都是有效结点（即可能存在不在链表上的结点），对数组进行排序从而把有效结点移到数组左端。
bool cmp(Node a,Node b){ if(a.XXX==-1||b.XXX=-1){ //至少一个结点是无效结点，就把它放到数组后面 return a.XXX>b.XXX; }else{ //第二级排序 } }
