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

两个链表的第一个公共结点：最直观的想法是，首先计算链表1和链表2的长度以及链表1与链表2的差值长度diff，然后将长度较大的那个链表走diff步，接着两个链表一起走并判断是否相等，如果是则返回该相等的公共结点，注意，由于此处没有头结点，故不需要判断当前链表的下一个是否想等，而是直接判断当前链表是否想等即可。

	// 求链表长度
	int GetLength(ListNode *pLink)
	{
		int len=0;
		while(pLink)
		{
			len++;
			pLink=pLink->next;
		}
		return len;
	}
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
		// 如果有一个为空则返回空
        if(!pHead1||!pHead2)
			return nullptr;
		// 首相同
		// if(pHead1==pHead2)
		// 	return pHead1;
		// 求链表1长度
		int l1=GetLength(pHead1);
		// 求链表2长度
		int l2=GetLength(pHead2);
		// 求l1和l2差值
		int diff=l1>l2?l1-l2:l2-l1;
		ListNode* p1=pHead1;
		ListNode* p2=pHead2;
		// l1>l2 l1走l1-l2步
		if(l1>l2)
		{
			for(int i=1;i<=diff;i++)
				p1=p1->next;
		}
		// l2>l1 l2走l2-l1步
		else 
		{
			for(int i=1;i<=diff;i++)
				p2=p2->next;
		}
		// cout<<p1->val<<endl;
		// cout<<p2->val<<endl;
		ListNode* result;
		//一起走
		while(p1&&p2)
		{
			if(p1==p2)
			{
				result=p1;
				break;
			}
			p1=p1->next;
			p2=p2->next;
		}
		return result;
    }

idea：上述方法还分别计算了链表1和链表2的长度，那么有没有什么方法不计算链表的长度也能找到第一个公共结点呢？有！使用两个指针N1和N2，N1从链表1的开头开始遍历，如果遍历完则继续从链表2的开头开始遍历，N2从链表2的开头开始遍历，如果遍历完则继续从链表1的开头开始遍历。由于两个指针同样的速度走完L1+L2相同的长度，故当两者相等且不为空的时候必然是公共结点或者无公共结点走到链表结尾两者均为空。(可手动模拟过程)

ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) 
{
	ListNode* L1=pHead1;
	ListNode* L2=pHead2;
	while(L1!=L2)
	{
		L1=(L1==nullptr)?pHead2:L1->next;
		L2=(L2==nullptr)?pHead1:L2->next;
	}
	return L1;
}