[PAT解题报告] Sharing
单向链表求交点问题。
经典题，题目给的链表方式比较诡异，直接给的地址（5位int)，所以地址可以直接放数组下标里。两个链表先分别求长度，如果一个长度为x,一个长度为y，我们先沿着较长的走|x
- y|那么长，使得剩余部分一样长，再两个一起走下去，看看到达结尾前有没有相遇。就好像一个
"Y"字型，两个“分叉”不一样长，先把较长的砍掉一些，使得它们一样长了，再一起走就能找到交点了。
不要轻易用cin, cout。
代码：
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int add[100002];
int main() {
int x,y,z;
for (scanf("%d%d%d",&x,&y,&z);z;--z) {
int where;
char s[10];
int to;
scanf("%d%s%d",&where,s,&to);
add[where] = to;
}
int lenx = 0;
for (int i = x; i >= 0; ++lenx, i = add[i])
;
int leny = 0;
for (int i = y; i >= 0; ++leny, i = add[i])
;
for (int i = lenx - leny; i > 0; --i, x = add[x])
;
for (int i = leny - lenx; i > 0; --i, y = add[y])
;
for (; (x >= 0) && (y >= 0) && (x != y); x = add[x], y = add[y])
;
if (x >= 0) {
printf("%05d\n",x);
}
else {
puts("-1");
}
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1032
腾讯成长空间 6021人发布
