输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
解题思路
- 暴力枚举（O(m*n)）
- 辅助栈（两个栈）
- 双指针（O(m+n)）
上代码（C++很香）
法一：暴力枚举
ListNode* FindFirstCommonNodeBL( ListNode* pHead1, ListNode* pHead2) {
ListNode* pNode1 = pHead1;
ListNode* pNode2 = pHead2;
while(pNode1 != nullptr){
pNode2 = pHead2;
while(pNode2 != nullptr){
if(pNode1 == pNode2)
return pNode1;
pNode2 = pNode2->next;
}
pNode1 = pNode1->next;
}
return nullptr;
}
法二：辅助栈
注意，在判断栈顶元素的时候，直到栈顶元素不相等时，可能是找到了第一个相等的节点，也可能是没有相等的节点。
ListNode *FindFirstCommonNode(ListNode *headA, ListNode *headB){
if(headA == nullptr || headB == nullptr)
return nullptr;
ListNode* p = headA;
ListNode* q = headB;
stack<ListNode* > stack_a;
stack<ListNode* > stack_b;
while(p != nullptr){
stack_a.push(p);
p = p->next;
}
while(q != nullptr){
stack_b.push(q);
q = q->next;
}
int sizeA = stack_a.size();
int tmp = 0;
while(!stack_a.empty() && !stack_b.empty()){
if(stack_a.top() != stack_b.top())
break;
else{
stack_a.pop();
stack_b.pop();
tmp++;
}
}
tmp = sizeA - tmp;
p = headA;
while(tmp--)
p = p->next;
return p;
}
法三：双指针（很妙）
这里先假设链表A头结点与结点8的长度 与 链表B头结点与结点8的长度相等，那么就可以用双指针。
- 初始化：指针
ta指向链表A头结点，指针tb指向链表B头结点 - 如果
ta == tb， 说明找到了第一个公共的头结点，直接返回即可。 - 否则，
ta != tb，则++ta，++tb
所以现在的问题就变成，如何让本来长度不相等的变为相等的？
假设链表A长度为a， 链表B的长度为b，此时a != b
但是，a+b == b+a
因此，可以让a+b作为链表A的新长度，b+a作为链表B的新长度。
// 双指针法
ListNode* FindFirstCommonNodeDouble(ListNode* pHead1, ListNode* pHead2){
if(pHead1== nullptr || pHead2 == nullptr)
return nullptr;
ListNode* pNode1 = pHead1;
ListNode* pNode2 = pHead2;
while(pNode1 != pNode2){
pNode1 = pNode1->next;
pNode2 = pNode2->next;
if(pNode1 != pNode2){
if(pNode1 == nullptr)
pNode1 = pHead2;
if(pNode2 == nullptr)
pNode2 = pHead1;
}
}
// 走到最后是pNode1 == pNode2 == nullptr
// 所以如果有相同的节点，则返回第一个，如果没有，就最后返回nullptr
return pNode1;
}