# PAT 解题报告 1032. Sharing (25)

## 题目描述：

To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, “loading” and “being” are stored as showed in Figure 1.

Figure 1

You are supposed to find the starting position of the common suffix (e.g. the position of “i” in Figure 1).

## 算法分析：

int counts[100001];
int linkList[100001];
int target = -1;

int main(void) {

int start1, start2;
int N;

for(int i=0; i<100001; i++){
counts[i] = 0;
linkList[i] = -1;
}
cin>>start1>>start2>>N;
if(start1 == start2){
printf("%0.05d\n",start1);
return 0;
}

while(N--) {
int value1, value2;
char s2;
cin>>value1>>s2>>value2;
linkList[value1] = value2;
}

for(int s = start1; s!= -1; s = linkList[s])
counts[s] = 1;
int t;
int flag = 0;
for(t = start2; t!=-1 && !counts[t]; t = linkList[t]){
counts[t] = 1;
}

if(-1 != t)
printf("%.05d\n", t);
else
printf("-1\n");
return 0;

}

## Summary

PAT 1032. Sharing: 求两个链表的公共尾巴的第一个公共节点. 直接模拟, 标记第一个链表中节点的出现情况, 然后扫描第二个链表搜索第一个已经出现的节点即公共节点.

Written on August 2, 2013