时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
题目描述
输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
思路：
1、两个相交的链表呈Y型。找第一个公共结点，则第一个公共结点之后的next都是一样的，所以必然会有公共的尾部，所以，先找到这两个列表的长度差，让长链表先走长度差，然后再一起走。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
int len1 = findListLenth(pHead1);
int len2 = findListLenth(pHead2);
if(len1 > len2)
{
pHead1 = walkStep(pHead1,len1-len2);
}
else
{
pHead2 = walkStep(pHead2,len2-len1);
}
while(pHead1 != NULL)
{
if(pHead1 == pHead2)
return pHead1;
pHead1 = pHead1->next;
pHead2 = pHead2->next;
}
return NULL;
}
int findListLenth(ListNode *pHead)
{
int len = 0;
while(pHead != NULL)
{
len++;
pHead = pHead->next;
}
return len;
}
ListNode* walkStep(ListNode *pHead,int len)
{
while(len--)
{
pHead = pHead->next;
}
return pHead;
}
};
2、不找长度。设置两个指针p1,p2分别指向pHead1,pHead2,两个指针一起走，当短链表先指向NULL，让该指针指向另一个链表指针，最终两个指针到达NULL或公共结点
/*
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;
while(p1 != p2)
{
p1 = (p1 == NULL ? pHead2:p1->next);
p2 = (p2 == NULL ? pHead1:p2->next);
}
return p1;
}
};