题目描述：

输入两个链表，找出它们的第一个公共结点。

实现如下：

//节点结构体定义
struct ListNode 
{
	int val;
	struct ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

方法一

//利用两个栈，从头开始遍历两个链表，将其节点的地址分别存入两个栈中
//最终链表尾在栈顶
//依次出栈，记录公共节点的地址，最后的值就是两个链表的第一个公共节点
//注意
//1.判断链表是否存在
//2.有可能不存在公共节点
//3.两个链表有可能不一样长
class Solution 
{
public:
	ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) 
	{
		//防御性动作，判断链表是否存在
		if (pHead1 == NULL || pHead2 == NULL) return NULL;
		
		stack<ListNode*> p1Stk;
		stack<ListNode*> p2Stk;
		while (pHead1 != NULL)//遍历pHead1链表，记录节点地址并入栈
		{
			p1Stk.push(pHead1);
			pHead1 = pHead1->next;
		}
		while (pHead2 != NULL)//遍历pHead2链表，记录节点地址并入栈
		{
			p2Stk.push(pHead2);
			pHead2 = pHead2->next;
		}
		ListNode* tmp = NULL;//记录公共节点的地址
		while (!p1Stk.empty() && !p2Stk.empty())//有可能出现不存在公共节点的情况
		{
			if (p1Stk.top() == p2Stk.top())//栈顶元素值相等
			{
				tmp = p1Stk.top();//记录值
				p1Stk.pop();//出栈顶元素
				p2Stk.pop();//出栈顶元素
				continue;
			}
			else//如果栈顶元素不相等，则终止循环，return公共节点
				return tmp;
		}
		return tmp;//有可能出现不存在公共节点的情况
	}
};

方法二

//方法一中使用了辅助内存空间，使得空间复杂度为O(m+n)
//方法二中保证遍历链表的指针从相同个数的节点开始遍历，即让两个链表的长度变得一样
//第一次遍历计算出两个链表的长的
//第二次遍历，让长的链表先移动差值个节点，然后两个链表在一同开始遍历
class Solution
{
public:
	ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2)
	{
		//防御性动作
		if (pHead1 == NULL || pHead2 == NULL) return NULL;
		int node1Num = 0;//记录pHead1的长度
		int node2Num = 0;//记录pHead2的长度
		ListNode* p1 = pHead1;
		ListNode* p2 = pHead2;

		while (p1 != NULL)//第一次遍历
		{
			++node1Num;
			p1 = p1->next;
		}
			
		while (p2 != NULL)//第二次遍历
		{
			++node2Num;
			p2 = p2->next;
		}

		p1 = pHead1;
		p2 = pHead2;
		int tmp = node1Num - node2Num;//计算两个链表的长度差
		while (tmp > 0)//pHead1长时，先移动
		{
			p1 = p1->next;
			--tmp;
		}
		while (tmp < 0)//pHead2长时，先移动
		{
			p2 = p2->next;
			++tmp;
		}
		while (p1 != p2)//之后开始一同移动
		{
			p1 = p1->next;
			p2 = p2->next;
		}
		return p1;//有可能不存在公共节点
	}
};

方法三

//大神做法！！！
//代码如此简单。。但想法如此巧妙！！！
//不再利用第一次遍历，来记录两个链表的长度
//而是利用类似判断链表是否有环的思路（不知道这样理解对不对）
//当没有公共节点时，依旧返回NULL                                                                                                                                            
class Solution 
{
public:
	ListNode* FindFirstCommonNode(ListNode *pHead1, ListNode *pHead2) 
	{
		ListNode *p1 = pHead1;
		ListNode *p2 = pHead2;
		while (p1 != p2) 
		{
			p1 = (p1 == NULL ? pHead2 : p1->next);
			p2 = (p2 == NULL ? pHead1 : p2->next);
		}
		return p1;
	}
};