PAT A1032 Sharing（静态链表）

本文主要是介绍PAT A1032 Sharing（静态链表），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

给定连个单词，判断两个单词相同后缀的位置。
在这里插入图片描述

Input

第一行start1 start2 N，其中start1第一个单词地址，start2为第二个单词地址，N为一共N个节点。

Sample Input 1:

11111 22222 9
67890 i 00002
00010 a 12345
00003 g -1
12345 D 67890
00002 n 00003
22222 B 23456
11111 L 00001
23456 e 67890
00001 o 00010

Sample Output 1:

67890

Sample Input 2:

00001 00002 4
00001 a 10001
10001 s -1
00002 a 10002
10002 t -1

Sample Output 2:

-1

Solution

链表的数据量不太大，可以使用静态链表。遍历第一个链表，每遍历一个节点标记一下flag为true，遍历第二个链表时判断该节点是否为true，如果是true则该节点就是两者公共节点。

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 100000;
struct Edge
{char data;int next;bool flag; //flag表示有没有访问过一次
};
Edge edges[maxn];
int main()
{// freopen("in.txt", "r", stdin);int start1, start2, N;while (~scanf("%05d%05d%d", &start1, &start2, &N)){for (int i = 0; i < maxn; i++) //初始化为未访问过edges[i].flag = false;for (int i = 0; i < N; i++) //输入数据{int tmp_start, tmp_next;char tmp_data;scanf("%05d %c %05d", &tmp_start, &tmp_data, &tmp_next);edges[tmp_start].data = tmp_data;edges[tmp_start].next = tmp_next;}for (int p = start1; p != -1; p = edges[p].next)edges[p].flag = true; //遍历第一个链表int p;for (p = start2; p != -1; p = edges[p].next){if (edges[p].flag == true) //若被遍历过一次则记录pointer位置break;}if (p == -1)printf("%d\n", p);elseprintf("%05d\n", p);}return 0;
}