PAT | Advanced 1032 Sharing 25‘ （共用结点）

 思路：如果有公共结点 说明两者从公共结点开始向后遍历能够同时到达NULL(-1);

利用这个性质，设置两个工作指针p,q（其实就是链表的数组下标）分别指向两个链表的头地址，只需获取两个链表的长度，然后调整工作指针的位置，使得两个工作指针到其链表尾的距离相当即可；

这时我们只需同步让指针后移，如果p==q，代表两个指针指向同一地址，即共享结点，此时返回p即可。

#include 
#include 
using namespace std;

const int MaxN = 100100;

struct LNode {
	int next;
	char data;
}LNode[MaxN];

int main() {
	int Head1, Head2, N;					//链表1首地址，链表2首地址，长度
	cin >> Head1 >> Head2 >> N;

	for (int i = 0; i < N; i++) {			//初始化输入数据
		int temp;
		cin >> temp;
		cin >> LNode[temp].data >> LNode[temp].next;
	}

	int len1 = 0, len2 = 0, pos;			//遍历链表1 链表2 长度
	pos = Head1;
	while (pos != -1) {
		len1++;
		pos = LNode[pos].next;
	}
	pos = Head2;
	while (pos != -1) {
		len2++;
		pos = LNode[pos].next;
	}

	if (len1 * len2 == 0) {					//判断 若有空链表 则终止
		cout << "-1"; exit(0);
	}

	int p = Head1, q = Head2;				//调整长度 使两链表到NULL的距离相等 
											//p,q分别为链表1,2的工作指针
	if (len1 > len2) {
		int delta = len1 - len2;
		while (delta--) {
			p = LNode[p].next;
		}
	}
	else if (len2 > len1) {
		int delta = len2 - len1;
		while (delta--) {
			q = LNode[q].next;
		}
	}

	int index = -1, flag = 0;			//index用于指示位置
	while (flag == 0) {
		if (LNode[p].next == -1 || LNode[q].next == -1) {
			flag = 1; index = -1;		//查找到NULL了 则说明无公共结点 返回index=1
										//感觉这里不太严谨 毕竟最后一个结点也可能是公共结点 但是测试案例能通过就没管了
		}
		else if (p == q) {              //如果p=q 说明地址相同 用index指示
			index = p; flag = 1;
		}
		else {						   //否则 工作指针后移
			p = LNode[p].next; q = LNode[q].next;
		}
	}

	if (index == -1)
		cout << "-1";
	else {
		cout.fill('0'); 
		cout << setw(5) << index;
	}
	return 0;

}