题解 | #Sharing#

#include <iostream>
using namespace std;

struct node {
    char data;
    int next;
};

int main() {
  	// word1、word2是两个单词的首地址, addr用于输入，实际上不存储数据
    int word1, word2, n, addr;
    node a[100005] = {0};
    while ( cin >> word1 >> word2 >> n ) {
        for (int i = 0; i < n; i++) {
            cin >> addr;
            cin >> a[addr].data >> a[addr].next;
        }
        int p = word1, q = word2;
	    // 计算两个单词的长度
        int size1 = 0, size2 = 0;
        while ( p != -1 ) {
            p = a[p].next;
            size1++;
        }
        while ( q != -1 ) {
            q = a[q].next;
            size2++;
        }
        int d = size1 - size2;
        p = word1;
        q = word2;
	    // 长度较长的单词先走d步，两个while只会执行其中一个
        while ( d > 0 ) {
            p = a[p].next;
            d--;
        }
        d = size2 - size1;
        while ( d > 0 ) {
            q = a[q].next;
            d--;
        }
	  // 找到第一个相同节点
	  // 注意地址相同才是相同节点，数据相同不一定是相同节点
        while ( p != q && p != -1 && q != -1 ) {
            p = a[p].next;
            q = a[q].next;
        }
        cout << p << endl;
    }
    return 0;
}