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

#include <cstdlib>
//两种解法，比较常规的就是快慢指针，先算出两条链表的长度，然后让快指针指向长的那一条，让它先走delta步，接着再快慢指针一起走，这样就能正好走到入口处了。
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2)
	{
		return FindFirstCommonNode_2(pHead1,pHead2);
	}
	ListNode* FindFirstCommonNode_2( ListNode* pHead1, ListNode* pHead2)
	{
		int p1Length,p2Length=0;
		auto getlength=[](ListNode* p)->int
		{
			ListNode*current=p;
			int result=0;
			while(current!=nullptr)
			{
				result++;
				current=current->next;
			}
			return result;
		};
		p1Length=getlength(pHead1);
		p2Length=getlength(pHead2);
		ListNode* longer=p1Length>p2Length? pHead1:pHead2;
		ListNode* shorter=p1Length>p2Length? pHead2:pHead1;
		int delta=abs(p2Length-p1Length);
		for(int i=0;i<delta;i++)
			longer=longer->next;
		while(longer && shorter && longer!=shorter)
		{
			longer=longer->next;
			shorter=shorter->next;
		}
		return longer;
	}

    ListNode* FindFirstCommonNode_1( ListNode* pHead1, ListNode* pHead2) {
		ListNode*p1=pHead1;
		ListNode *p2=pHead2;
		//这种做法的时间复杂度是O(n^2)
		// while (p1!=p2) {
		// 	p1=p1? p1->next:pHead1;
		// 	p2=p2? p2->next:pHead2;
		// }
		//参考了题解https://blog.nowcoder.net/n/faa595fd79d645b4935c115a1e406a96?f=comment
		while (p1!=p2) {//这种做法非常精妙，从代码上实现了两个链表的连接，而不是在内存上进行连接（因为如果在内存上进行连接的话，两个链表的尾巴实际上是同一个对象，是没法实现的）。
		//为了解释这种做法，我们将链表1的非公共部分定义为x1，公共部分定义为y。x2同理。
		//这种做法就是让p1和p2指针都完整的把两个链表各走完一次。而由于p1指针以x1+y+x2的路径行走，让p2以x2+y+x1的路径行走。在走完了这两段路径后二者剩下的都正好是第二次的公共部分。
			p1=p1? p1->next:pHead2;
			p2=p2? p2->next:pHead1;
		}
		return p1;
    }
};