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

和官方题解稍微不同的思路。先构造一个环（将链表1连上链表2），然后再找到环的入口即可。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
	// 1. 构造环
	// 2. 找环的入口
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
		if(pHead1==nullptr||pHead2==nullptr) return nullptr;
		auto start = pHead1;
		while(start->next!=nullptr){
			start = start->next;
		}
		auto lastNode = start;
		start->next = pHead2;
		start = start->next;
		while (true) {
			start = start->next;
			if(start == nullptr) return nullptr;
			if(start == pHead2) break;
		}
		//找环头
		auto fast = pHead1;
		auto slow = pHead1;
		fast = fast->next->next;
		slow = slow->next;
		while(fast!=slow){
			fast = fast->next->next;
			slow = slow->next;
		}
		fast = pHead1;
		while(fast!=slow){
			slow=slow->next;
			fast=fast->next;
		}
		lastNode->next = nullptr;
		return fast;
    }
};