算法1:单链表的遍历() $O(n)$
//用一个数组标记地址是否出现
#include <bits/stdc++.h>
using namespace std;
const int N = 1E5+10;
int e[N], ne[N], h1, h2, n;
bool st[N]; //标记地址是否出现
int main() {
scanf("%d%d%d", &h1, &h2, &n);
for (int i = 0; i < n; ++ i) {
int addr, nex;
char data;
scanf("%d %c %d", &addr, &data, &nex); //注意char型变量在scanf的时候会吃空格
e[addr] = data;
ne[addr] = nex;
}
for (int i = h1; ~i; i = ne[i]) st[i] = 1; //遍历第一个单链表,标记出现的节点
int res = -1;
for (int i = h2; ~i; i = ne[i]) //遍历第二个单链表
if (st[i]) {
printf("%05d", res);
return 0;
}
printf("-1");
return 0;
}
算法2:扫描两个单链表,扫完后到扫另一个() $O(n)$
//将两条链表长度划分为X + Z, Y + Z (Z为公共部分)
// 到达链尾就从另一个链表头结点继续走
// 1. 如果共享一个子链 X + Z + Y = Y + Z + X 一定在相交的子链入口处结束
// 2. 如果不同共享子链 X + Y = Y + X 到达链尾结束
#include <bits/stdc++.h>
using namespace std;
const int N = 1E5+10;
int e[N], ne[N], h1, h2, idx, n;
int main() {
scanf("%d%d%d", &h1, &h2, &n);
for (int i = 0; i < n; ++ i) {
int addr, nex;
char data;
scanf("%d %c %d", &addr, &data, &nex); //注意输入字符 中间加入空格
e[addr] = data;
ne[addr] = nex;
}
int i = h1, j = h2;
while (i != j) {
i = (i==-1 ? h2 : ne[i]);
j = (j==-1 ? h1 : ne[j]);
}
if (i == -1 || j == -1) printf("-1");
else printf("%05d", i);
return 0;
}