title
输入两个链表，找出它们的第一个公共结点。
solution
设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。
当访问 A 链表的指针访问到链表尾部时，令它从链表 B 的头部重新开始访问链表 B；同样地，当访问 B 链表的指针访问到链表尾部时，令它从链表 A 的头部重新开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。
找出2个链表的长度，然后让长的先走两个链表的长度差，然后再一起走 （因为2个链表用公共的尾部）
/*
找出2个链表的长度，然后让长的先走两个链表的长度差，然后再一起走
（因为2个链表用公共的尾部）
*/
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 *pHead1){
if(pHead1 == NULL) return 0;
int sum = 1;
while(pHead1 = pHead1->next) sum++;
return sum;
}
ListNode* walkStep(ListNode *pHead1, int step){
while(step--){
pHead1 = pHead1->next;
}
return pHead1;
}
};
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode l1 = pHead1, l2 = pHead2;
while (l1 != l2) {
l1 = (l1 == null) ? pHead2 : l1.next;
l2 = (l2 == null) ? pHead1 : l2.next;
}
return l1;
}