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

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution 
{
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) 
	{
		// 边界条件：如果任一链表为空，直接返回空（不可能有公共节点）
		if(pHead1 == nullptr || pHead2 == nullptr) return nullptr;
		
		// 定义两个指针，分别从两个链表的头节点开始遍历
		ListNode* cur1 = pHead1, *cur2 = pHead2;
		
		// 循环条件：当两个指针指向的节点不同时，继续遍历
		// 当两指针相遇时（指向同一节点），该节点即为第一个公共节点（或同时为nullptr）
		while(cur1 != cur2)
		{
			// 指针1的移动规则：
			// 如果当前节点不为空，继续向后移动；如果为空，切换到另一个链表的头节点
			cur1 = cur1 ? cur1->next : pHead2;
			// 指针2的移动规则：与指针1对称
			cur2 = cur2 ? cur2->next : pHead1;
		}
		
		// 退出循环时，cur1 == cur2，此时要么是公共节点，要么都是nullptr（无公共节点）
		return cur1;
    }
};