题目描述

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

方法1(使用set)

思路

利用unordered_set容器存放数据不重复的思想，将链表1的节点全都放进unordered_set容器中去，然后遍历链表2，在容器中找有没有链表2的节点，第一次找到的节点就是两个链表的第一个公共节点

代码

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        unordered_set<ListNode*> s;
        ListNode* p1=pHead1;
        ListNode* p2=pHead2;
        while(p1!=NULL)
        {
            s.insert(p1);
            p1=p1->next;
        }
        //unordered_set<ListNode*>::iterator pos;
        while(p2!=NULL)
        {

            if(s.find(p2)!=s.end())
                return p2;
            p2=p2->next;
        }
        return NULL;
    }
};

方法2(快慢指针思想)

思路

• 首先计算出两个链表的长度
• 让长的链表指针先走差值步
• 两个指针同时走，直到相遇(相遇时的节点即为链表的第一个公共节点)

代码

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if(pHead1==NULL||pHead2==NULL)
            return NULL;
        ListNode* p1=pHead1;
        ListNode* p2=pHead2;
        int len1=0,len2=0;
        int k=0;
        while(p1!=NULL)
        {
            len1++;
            p1=p1->next;
        }
        p1=pHead1;
        while(p2!=NULL)
        {
            len2++;
            p2=p2->next;
        }
        p2=pHead2;
        if(len1>len2)
        {
            k=len1-len2;
            while(k)
            {
                p1=p1->next;
                k--;
            }
        }
        else
        {
            k=len2-len1;
            while(k)
            {
                p2=p2->next;
                k--;
            }
        }
        while(p1!=NULL&&p2!=NULL&&p1!=p2)
        {
            p1=p1->next;
            p2=p2->next;
        }
        return p2;
        }
};

这个方法有个问题；上面代码的最后一个while我一开始是这么写的,然后就只通过了42.86，这是为什么嘞：