题目地址:https://pintia.cn/problem-sets/994805342720868352/problems/994805460652113920

题目解释:

给出两条链表的首地址及若干结点的地址、数据、下一个结点的地址,求两条链表的首个共用结点的地址,如果两条链表没有共用结点,则输出-1。

解题思路:

遍历第一条链表,对结点都做个标记,再遍历第二条链表,如果遇到的结点已经被标记过了,则输出,都没有则输出-1。

静态链表:

当结点的地址是比较小的数(如5位整数时),不用去建立动态链表,可以建立结构体数组,数组的下标直接表示结点的地址

struct NODE{
    char data;
    int next;
}node[maxn];//结构体的类型名和变量名不要相同

node[22222]=333333;地址为22222的结点的下一个结点的地址为33333

ac代码:

#include <iostream>
#include <cstring>
#define maxn 100005
using namespace std;
struct NODE{
    char data;
    int next;
    bool flag;
}node[maxn];
int main()
{
    int n,a1,a2,i,address,next;
    char data;
    scanf("%d%d%d",&a1,&a2,&n);
    for(i=0;i<n;i++)
    {
        scanf("%d %c %d",&address,&data,&next);
        node[address].data=data;
        node[address].next=next;
        node[address].flag=false;
    }
    for(i=a1;i!=-1;)
    {
        node[i].flag = true;
        i = node[i].next;
    }
    for(i=a2;i!=-1;)
    {
        if(node[i].flag==true) break;
        i=node[i].next;
    }
    if(i!=-1) printf("%05d\n",i);
    else printf("-1\n");
    return 0;
}