关于算法-数据结构:PAT甲级1032-Sharing

题目粗心:

给定两条链表的首地址和若干结点地址、数据、下一个结点的地址, 求两条链表的公共节点地址, 如果没有输入 -1。

算法思路：

因为之前在考 408 做过做过题, 所以思路用的就是王道书上讲的 (过了良久还记得,$ε=(′ο`*)))$ 唉 ), 咱们应用 $node$ 数组存储所有输出的节点，应用 $word1$ 存储第一个单词组成的链表，$word2$ 存储第二个单词组成的链表。咱们首先遍历 $node$ 数组，获取 $word1$ 链表和其长度 $lengthOfWord1$，$word2$ 链表和其长度 $lengthOfWord2$. 而后让长度更长的链表的头指针先向前走 $|lengthOfWord1-lengthOfWord2|$ 步，而后再让 $word1$ 和 $word2$ 的工作指针同时向后走，在指针相遇的时候就退出循环，如果以后指针的地址为 -1，则输入 -1，否则保留 5 位数输入地址。

留神点：

1、地址得保留 5 位输入。
2、输出的时候得加空格，因为 %c 能够承受空格。

提交后果：

AC 代码：

#include <cstdio>

using namespace std;

struct Node{
    int address;
    char data;
    int next;
}node[100005],word1[100005],word2[100005];

int main(){
    int begin_word1,begin_word2,N;
    scanf("%d %d %d",&begin_word1,&begin_word2,&N);
    Node p{};
    for (int i = 0; i < N; ++i) {scanf("%d %c %d",&p.address,&p.data,&p.next);
        node[p.address] = p;
    }
    int lengthOfWord1=0,lengthOfWord2=0;
    for (int address=begin_word1;address!=-1;address=node[address].next) {p.address = node[address].address;
        p.data = node[address].data;
        p.next = node[address].next;
        word1[p.address] = p;
        ++lengthOfWord1;
    }
    for (int address=begin_word2;address!=-1;address=node[address].next) {p.address = node[address].address;
        p.data = node[address].data;
        p.next = node[address].next;
        word2[p.address] = p;
        ++lengthOfWord2;
    }
    if(lengthOfWord1>lengthOfWord2){
        // begin_word1 先走 lengthOfWord1-lengthOfWord2 步
        for (int i = 0; i < lengthOfWord1 - lengthOfWord2; ++i) {begin_word1 = word1[begin_word1].next;
        }
    } else {
        // begin_word2 先走 lengthOfWord2-lengthOfWord1 步
        for (int i = 0; i < lengthOfWord2 - lengthOfWord1; ++i) {begin_word2 = word2[begin_word2].next;
        }
    }
    // 而后两者同时后退, 相遇的时候要么是独特的节点，要么是 -1
    while (begin_word1!=begin_word2){begin_word1 = word1[begin_word1].next;
        begin_word2 = word2[begin_word2].next;
    }
    if(begin_word1==-1){printf("-1");
    } else {printf("%05d",begin_word1);
    }
    return 0;
}