30.两个链表的第一个公共节点

题目：两个不带环的链表，找到他们的第一个公共子节点。

技巧：链表可以确定最后一个节点，可以通过遍历的方式确定长度，可以通过快慢指针来打个长度差，也可以运用集合map、set来找对应关系

难点：
思路1在决定哪个链表先走的时候容易造成冗余代码，可以设置2个指针，1个指向长链表，1个指向短链表，避免冗余代码

思路1：

• 如果两个链表有公共节点，那么经过公共节点后两个链表就变成了一个链表（因为指向下一节点的指针只有1个）
• 所以先找到两个链表的最后一个节点判断相等不相等，相等就说明2个链表有公共节点。 不相等就说明没有。
• 若有公共节点，那么通过上一步可以得出两个链表的长度，让长链表先走出多余的长度，然后两个链表同时前进，当指向同一个节点时，就是第一个公共节点

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if(pHead1==nullptr||pHead2==nullptr)
            return nullptr;
        ListNode *p1=pHead1,*p2=pHead2,*end1,*end2;
        int len1=1,len2=1;
        while(p1->next!=nullptr){
            len1++;
            p1=p1->next;
        }
        end1=p1;
        while(p2->next!=nullptr){
            len2++;
            p2=p2->next;
        }
        end2=p2;
        if(end1!=end2)
            return nullptr;
        if(len1>len2){
            p1=pHead1;
            p2=pHead2;
        }
        else{
            p1=pHead2;
            p2=pHead1;
        }
        int step=len1>len2?len1-len2:len2-len1;
        for(int i=0;i<step;i++)
            p1=p1->next;
        while(p1!=p2){
            p1=p1->next;
            p2=p2->next;
        }
        return p1;
        
    }
};

另一个思路：
运用集合set来解决，因为集合set只能放入不重复的元素，把第一个链表的各个节点放入set，然后遍历第2个链表的节点，查看集合set中有没有该节点，第一次发现有的时候就是第一个公共节点

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if(pHead1==nullptr||pHead2==nullptr)
            return nullptr;
        set<ListNode *> rec;
        ListNode *p1=pHead1,*p2=pHead2;
        while(p1){
            rec.insert(p1);
            p1=p1->next;
        }
        while(p2){
            if(rec.find(p2)!=rec.end())
                return p2;
            p2=p2->next;
        }
        return p2;
        
    }
};