两个链表的第一个公共结点

主要分析了链表尾部有环的时候怎么处理，无环的解法参考selfboot。

两个无环的链表

当链表无环时，分为有交点和无交点，而每种情况下又分为等长和不等长。当链表等长时，同时从头遍历两个链表，最晚在第一次遍历完成时就能判断并返回交点；当其不等长时，某链表遍历完成，使其指向另一个链表的头结点，在第二次遍历时就能找出相同的结点或者返回NULL。

	ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2)
	{
		if (pHead1 == NULL || pHead2 == NULL) return NULL;
		ListNode* p1 = pHead1;
		ListNode* p2 = pHead2;
		while (p1 != p2){
			p1 = (p1 == NULL ? pHead2 : p1->next);
			p2 = (p2 == NULL ? pHead1 : p2->next);
		}
		return p1;
	}

两个尾部有环的链表

需要先检索两个链表的环入口结点，即loop点。 ①如果loop点相同：解法同无环的解法，只不过拼接点改为了loop点。同Loop ②如果loop点不同：当p1点从loop出发，第一次回到loop1前，若相遇loop2，则相交，否则无交点。不同Loop

	ListNode* bothLoop(ListNode* pHead1, ListNode* loop1, ListNode* pHead2, ListNode* loop2){
		ListNode* p1 = NULL;
		ListNode* p2 = NULL;
		if (loop1 == loop2){
			while (p1 != p2){
				p1 = (p1 == loop1 ? pHead2 : p1->next);        //解法同无环解法，拼接点设置为loop点即可。
				p2 = (p2 == loop1 ? pHead1 : p2->next);
			}
			return p1;
		}
		else {
			p1 = loop1->next;                                  //当p1点从loop出发，第一次回到loop1前，若相遇loop2，则相交，否则无交点。
			while (p1 != loop1){
				if (p1 == loop2){
					return loop1;
				}
				p1 = p1->next;
			}
			return NULL;
		}
	}

附上完整代码

class Solution{
public:
	ListNode* EntryNodeOfLoop(ListNode* pHead)
	{
		if (pHead == NULL || pHead->next == NULL)
			return NULL;
		ListNode* p1 = pHead->next;                  //慢指针，一次前进一格
		ListNode* p2 = pHead->next->next;			 //快指针，一次前进两格
		while (p1 != p2)
		{
			if (p2 == NULL || p2->next == NULL)      //如果快指针p2走到头了，说明链表不成环
			{
				return NULL;
			}
			p1 = p1->next;                           //快慢前进
			p2 = p2->next->next;
		}                                            //假如成环，会在p1、p2相遇时结束第一个while。此时p1到入口的距离等于head到入口的距离
		p2 = pHead;                                  //让p2指向链表头部，p1位置不变。
		while (p1 != p2)
		{
			p1 = p1->next;
			p2 = p2->next;
		}
		return p1;                                   //p1, p2每次走一步直到p1 == p2; 此时p1指向环的入口。
	}

	ListNode* bothLoop(ListNode* pHead1, ListNode* loop1, ListNode* pHead2, ListNode* loop2){
		ListNode* p1 = NULL;
		ListNode* p2 = NULL;
		if (loop1 == loop2){
			while (p1 != p2){
				p1 = (p1 == loop1 ? pHead2 : p1->next);        //解法同无环解法，拼接点设置为loop点即可。
				p2 = (p2 == loop1 ? pHead1 : p2->next);
			}
			return p1;
		}
		else {
			p1 = loop1->next;                                  //当p1点从loop出发，第一次回到loop1前，若相遇loop2，则相交，否则无交点。
			while (p1 != loop1){
				if (p1 == loop2){
					return loop1;
				}
				p1 = p1->next;
			}
			return NULL;
		}
	}

	ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2){
		if (pHead1 == NULL || pHead2 == NULL) return NULL;
		ListNode* p1 = pHead1;
		ListNode* p2 = pHead2;
		ListNode* loop1 = EntryNodeOfLoop(pHead1);            //查询是否有环的入口结点，并返回
		ListNode* loop2 = EntryNodeOfLoop(pHead2);
		if (loop1 == NULL && loop2 == NULL){                  //链表都无环解法，最坏时间复杂度O(m + n)
			while (p1 != p2){
				p1 = (p1 == NULL ? pHead2 : p1->next);
				p2 = (p2 == NULL ? pHead1 : p2->next);
			}
			return p1;
		}
		else if (loop1 != NULL && loop2 != NULL){             //链表都有环
			return bothLoop(pHead1,loop1,pHead2,loop2);
		}
		else{                                                 //一个有环一个无环，无交点
			return NULL;
		}

	}
};