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).

题目就是要你求两个链表的公共尾巴的第一个公共节点.

算法分析:

算法不难想到把应该. 首先从第一个链表头开始遍历链表1, 对每个节点进行标记(比如count = 1) 然后从第二个链表头开始遍历链表2, 当碰到一个节点是已经被标记了的, 那么这个节点就是第一个公共节点. 实现代码如下:

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