剑指36：求两个链表的第一个公共节点
两个链表的第一个公共结点
http://www.nowcoder.com/questionTerminal/6ab1d9a29e88450685099d45c9e31e46
总结一下，三种解法（C++实现）：
////////////////////////////////////////////
①stack解法：
两个链表先分别进栈
再依次出栈，从后向前遍历遇到第一个不相等的节点
再依次出栈，从后向前遍历遇到第一个不相等的节点
返回上一个相同节点即可
////////////////////////////////////////////
class Solution {
public:
ListNode* FindFirstCommonNode(ListNode* pHead1,ListNode* pHead2) {
ListNode* res = NULL;
if(!pHead1 || !pHead2)
return res;
stack<ListNode*> stack1;
stack<ListNode*> stack2;
while(pHead1){
stack1.push(pHead1);
pHead1 = pHead1->next;
}
while(pHead2){
stack2.push(pHead2);
pHead2 = pHead2->next;
}
if(stack1.top() != stack2.top())
return res;
while(stack1.size() != 0 && stack2.size() != 0){
res = stack1.top();
stack1.pop();
stack2.pop();
if(!stack1.empty() && !stack2.empty() && stack1.top() != stack2.top())
return res;
}
return res;
}
}; //////////////////////////////////////////// ②双指针解法：
连接两个链表，使两个指针遍历的长度相等，遇到第一个相同的节点返回即可
还有另一种先求出较长的链表，再做遍历其实原理一样，属同种解法
////////////////////////////////////////////
还有另一种先求出较长的链表，再做遍历其实原理一样，属同种解法
////////////////////////////////////////////
class Solution { public:
ListNode* FindFirstCommonNode(ListNode* pHead1,ListNode* pHead2) {
if(!pHead1 || !pHead2)
return NULL;
ListNode* p1 = pHead1;
ListNode* p2 = pHead2;
while(p1 != p2){
p1 = p1==NULL?pHead2:p1->next;
p2 = p2==NULL?pHead1:p2->next;
}
return p1;
}
}; //////////////////////////////////////////// ③map解法：
利用map的唯一键性质，先把链表1放入map中
再依次把链表2放进去，返回第一个值为2的键即可
////////////////////////////////////////////
再依次把链表2放进去，返回第一个值为2的键即可
////////////////////////////////////////////
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
unordered_map<ListNode*,int> m;
//将pHead1的节点全部放入map中
while(pHead1){
m[pHead1]++;
pHead1 = pHead1->next;
}
while(pHead2){
m[pHead2]++;
if(m[pHead2] == 2)
return pHead2;//如果存在，则返回
pHead2 = pHead2->next;
}
return pHead2;
}
}; 