剑指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的键即可
////////////////////////////////////////////

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;
    }
};