一、题目描述

JZ36两个链表的第一个公共结点
题目大意：给定两个链表A和B,他们尾部的几个结点可能是相同的,我们需要返回第一个公共结点的指针
注意审题：两个链表也可以没有公共结点,此时返回空指针即可

二、算法1（双指针）

算法思路

1.总体思路：我们可以分别用两个指针指向链表的头结点,然后一步一步地向后移动,当两个指针指向相同的结点时,直接返回即可
2.但是注意一个问题,由于两链表的长度不一定是相同的,因此我们需要预处理一下,保证两指针的相对位置重合
3.实现方法：先计算一下两条链表的长度len1, len2;若len1 > len2,则p1指针向后移动len1 - len2步;若len1 < len2,则p2指针向后移动len2 - len1步;len1 = len2时不变;这样预处理就完成了,最后两指针再同步向后移动即可

代码实现（C++11）

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        int len1 = get_ListLength(pHead1);
        int len2 = get_ListLength(pHead2);
        ListNode *p1 = pHead1, *p2 = pHead2;
        if(len1 > len2){
            while(len1 > len2){
                p1 = p1->next;
                --len1;
                }
            }
         if(len2 > len1){
             while(len2 > len1){
                 p2 = p2->next;
                 --len2;
                 }
             }
         while(p1){
             if(p1 == p2) return p1;
             p1 = p1->next;
             p2 = p2->next;
             }
        return p1;
    }

    int get_ListLength(ListNode* head){
        int len = 0;
        while(head){
            head = head->next;
            ++len;
            }
        return len;
    }
};

时间复杂度：O(n + m), n和m分别是链表A,B的长度
空间复杂度：O(1)

三、算法2（哈希集合）

算法思路

1.总体思路：我们先将其中一条链表的所有结点存下来,再遍历另一条链表,若查找到了相同的结点,则直接返回;若遍历完了都没有找到,就返回空指针

代码实现（C++11）

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        unordered_set<ListNode*> s;
        ListNode *p1 = pHead1, *p2 = pHead2;
        while(p1){
            s.insert(p1);
            p1 = p1->next;
            }
        while(p2){
            if(s.count(p2)) return p2;
            p2 = p2->next;
            }
        return nullptr;
    }
};

时间复杂度：O(n + m), n和m分别是链表A,B的长度
空间复杂度：O(n)