参考资料：
[1]剑指OFFER课本第3种解法
关键词：
先得到链表的长度，再归位指针。一个链表先走k步，然后两个一起走
注意：
统计完长度，记得把指针弄回原来的地方！！！！还有，两个链表可以没有公共节点。
自己的解法：
改进版：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
if (pHead1 == nullptr || pHead2 == nullptr)
return nullptr;
int nLen1, nLen2;
nLen1 = nLen2 = 0;
ListNode* pNode1 = pHead1;
ListNode* pNode2 = pHead2;
//步骤1:先统计链表1和链表2的长度
while (pNode1 != nullptr)
{
nLen1++;
pNode1 = pNode1->next;
}
while (pNode2 != nullptr)
{
nLen2++;
pNode2 = pNode2->next;
}
int nDiff = abs(nLen1-nLen2);
//步骤2：两个链表的长度相减，其中一个长的链表先走diff步，然后一起走
pNode1 = pHead1;
pNode2 = pHead2;
if (nLen1 >= nLen2)
{
while (nDiff--)
{
pNode1 = pNode1->next;
}
}
else
{
while (nDiff--)
{
pNode2 = pNode2->next;
}
}
//两个指针一起走，即使两个链表没有公共节点，也是可以的
while (pNode1 != pNode2)
{
pNode1 = pNode1->next;
pNode2 = pNode2->next;
}
return pNode1;
}
};
初始版：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
//思路：
//步骤1：各自统计两个链表的长度
//步骤2：得到两个链表的长度差，长的链表先走长度差的大小，然后一起走，如果相等就是第一个公共节点
if(pHead1 == nullptr || pHead2 == nullptr)
return nullptr;
//步骤1：各自统计两个链表的长度
ListNode* pNode1 = pHead1;
ListNode* pNode2 = pHead2;
int len1=0;
while(pNode1 != nullptr)
{
pNode1= pNode1->next;
len1++;
}
int len2 =0;
while(pNode2 != nullptr)
{
pNode2 = pNode2->next;
len2++;
}
//记得归位啊！！！！！！！！！！！！！！！！！！！！
pNode1 = pHead1;
pNode2 = pHead2;
//步骤2：得到两个链表的长度差，长的链表先走长度差的大小，然后一起走，如果相等就是第一个公共节点
int diff = 0;
if(len1>=len2)
{
diff = len1-len2;
for(int i =1;i<=diff;i++)
{
pNode1 = pNode1->next;
}
}
else
{
diff = len2-len1;
for(int i =1;i<=diff;i++)
{
pNode2 = pNode2->next;
}
}
while(pNode1 != pNode2)
{
pNode1 = pNode1->next;
pNode2 = pNode2->next;
}
return pNode1;
}
};
标准答案：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
//步骤1：找到链表的长度
ListNode* p1=pHead1;
ListNode* p2=pHead2;
int length1= 0,length2 = 0;
while(p1 != NULL)
{
p1 = p1->next;
length1++;
}
while(p2 != NULL)
{
p2 = p2->next;
length2++;
}
//步骤2：找到两个长度的差
int differ=0;
if(length1>length2)
{
differ= length1-length2;
p1 = pHead1;//长一点的
p2 = pHead2;
}
else
{
differ = length2-length1;
p1 = pHead2;//长一点的
p2 = pHead1;
}
//步骤3：长的先前进几步
for(int i=0;i<differ;i++)
{
p1 = p1->next;
}
//步骤4：找到公共节点
while(p1 != NULL)
{
if(p1 ==p2)
return p1;
p1= p1->next;
p2= p2->next;
}
return p1;
}
};
