题解 | #两个链表的第一个公共结点#

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        // 遍历两个链表长度，计算长度之差
		ListNode* p = pHead1;
		ListNode* q = pHead2;
		int m = 0, n = 0;
		while (p != nullptr) { m++; p = p->next; }
		while (q != nullptr) { n++; q = q->next; }
		p = pHead1;
		q = pHead2;
		
		// 长的链表先走diff步，diff为链表长度之差
		if (m > n) {
			int diff = m - n;
			while (diff--) { p = p->next; }
		} else {
			int diff = n - m;
			while (diff--) { q = q->next; }
		}

		// 同时向前遍历，寻找是否有公共节点
		while (p != nullptr && q != nullptr) {
			if (p == q)
				return p;
			p = p->next;
			q = q->next;
		}

		return nullptr;
    }
};