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

        解题思路1：找到两个链表的长度差，然后将较长的链表指针先走n步，然后两个指针分别走剩余的步数，就会同时到达第一个公共结点。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
				ListNode *p1 = pHead1;
		ListNode *p2 = pHead2;
		int cnt1 = 0,cnt2 = 0;
		while(p1)
		{
			cnt1++;
			p1 =p1->next;
		}
		while(p2)
		{
			cnt2++;
			p2 = p2->next;
		}
		if(cnt2>=cnt1)
		{
			for(int i = 0;i<cnt2-cnt1;++i)
			{
				pHead2 = pHead2->next;
			}
			while(pHead1 != pHead2)
			{
				pHead1 = pHead1->next;
				pHead2 = pHead2->next;
			}
		}
		else
		{
			for(int i = 0;i<cnt1-cnt2;++i)
			{
				pHead1 = pHead1->next;
			}
			while(pHead1 != pHead2)
			{
				pHead1 = pHead1->next;
				pHead2 = pHead2->next;
			}
		}
		return pHead1;
    }
};

        解题思路2：如果两个链表的长度相等，就可以慢慢遍历两个链表，直到找到相等的结点，如何使两个链表相等呢？可以将两个链表相加，这样长度就相等了

        将A+B作为新的链表A，将B+A作为新的链表B，这样长度就一致了，使用双指针遍历即可找到公共结点

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
		ListNode *p1 = pHead1;
		ListNode *p2 = pHead2;
		if(p1 == nullptr || p2 == nullptr)
			return nullptr;
		while(p1 != p2)
		{
			p1 = p1->next;
			p2 = p2->next;
			if(p1 != p2)
			{
				if(p1 == nullptr)
					p1 = pHead2;
				if(p2 == nullptr)
					p2 = pHead1;
			}
		}
		return p1;
    }
};