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

class Solution {
public:
    ListNode* FindFirstCommonNode( 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;
    }
};