两个链表的第一个公共结点

题目描述

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

思路

1.做这题时，我有许多想法，但其中一种做法最为简单粗暴，堪称邪门做法，和其他人的做法都不一样，因此记录下来。

正道做法

比较直接的做法是，让两个链表的长度相等，然后使用双指针即可。至于如何让两个链表的长度相等，就是将b链表拼接到a链表后，同时让a链表拼接到b链表后。

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode *ta = pHead1, *tb = pHead2;
        while (ta != tb) {
            ta = ta ? ta->next : pHead2;
            tb = tb ? tb->next : pHead1;
        }
        return ta;
    }
};

邪道做法

我的邪门做法非常简单粗暴，就是用哈希表作为标志数组，属于脑子都不动动的做法。当然如果用集合效果也差不多。

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        map<ListNode*,bool> m;
        while(pHead1){
            m[pHead1]=true;
            pHead1=pHead1->next;
        }
        while(pHead2){
            if(m.find(pHead2)!=m.end())
                return pHead2;
            m[pHead2]=true;
            pHead2=pHead2->next;
        }
        return nullptr;
    }
};