PAT_ Grade A_ 1032 Sharing

The main idea of the topic :

Given the first address and several node addresses of two linked lists 、 data 、 The address of the next node , Find the public node address of two linked lists , If no output -1.

Algorithm ideas ：

Because I was taking the exam before 408 Yes, I have , So the train of thought is what Wang daoshu says ( After a long time, I still remember ,$ε=(′ο｀*)))$ alas ), We use $node$ Array stores all input nodes , Use $word1$ Store the first word in a linked list ,$word2$ Store the second word in a linked list . Let's first traverse $node$ Array , obtain $word1$ List and its length $lengthOfWord1$,$word2$ List and its length $lengthOfWord2$. Then let the head pointer of the longer list go forward first $|lengthOfWord1-lengthOfWord2|$ Step , And then let $word1$ and $word2$ At the same time, the working pointer goes backward , Exit the loop when the pointers meet , If the address of the current pointer is -1, The output -1, Otherwise keep 5 Bits output address .

Be careful ：

1、 Keep the address 5 An output .
2、 You have to enter it with a space , because %c You can accept spaces .

Submit results ：

AC Code ：

#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 Go ahead lengthOfWord1-lengthOfWord2 Step 
        for (int i = 0; i < lengthOfWord1 - lengthOfWord2; ++i) {
            begin_word1 = word1[begin_word1].next;
        }
    } else {
        // begin_word2 Go ahead lengthOfWord2-lengthOfWord1 Step 
        for (int i = 0; i < lengthOfWord2 - lengthOfWord1; ++i) {
            begin_word2 = word2[begin_word2].next;
        }
    }
    //  And then both go forward at the same time , When we meet, it's either a common node , Or -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;
}