解法一 哈希表

解法一比较简单，考虑空间换时间。
1.遍历链表A，使用哈希表存储遍历过的节点；
2.遍历链表B，判断当前节点是否在1的哈希表中，如果在，返回该节点；如果不在，遍历下一节点；
3.如果B中所有节点都不在1的哈希表中，返回空。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_map<ListNode*, int> map;//存储A链表的哈希表
        ListNode* temp = headA;//指针计数器
        while(temp != nullptr){//遍历链表A
            map[temp]++;//存入哈希表中
            temp = temp -> next;
        }
        temp = headB;
        while(temp != nullptr){//遍历链表B
            if(map.count(temp)) return temp;//若存在公共节点，返回该节点
            temp = temp -> next;
        }
        return nullptr;//不存在公共节点，返回空
    }
};

复杂度分析

时间复杂度： O(m+n)。其中m为链表A长度，n为链表B长度，因为链表AB需要各遍历一次。
空间复杂度： O(m)。主要是哈希表存储链表A节点的开销。

解法二 双指针

考虑使用双指针降低空间复杂度。
1.判断链表是否都为空，如果都为空，返回空；
2.初始化指针temp1，temp2分别指向链表A和B的头结点，同时向后移动两个指针：
(1) 如果两个指针指向的节点相同，返回该节点；
(2) 如果其中一个指针为空，将该指针指向另一个链表的头结点。
这里对(1)做一下说明，如果两个指针都为空，说明不包含公共节点，返回空；如果两个指针指向同一个节点，说明该节点是两个链表的公共节点，返回该节点。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA==NULL || headB==NULL) return nullptr;
        temp1 = headA;
        temp2 = headB;
        while(!(temp1==temp2)){
            if(temp1==nullptr) temp1 = headB;
            else temp1 = temp1->next;
            if(temp2==nullptr) temp2 = headA;
            else temp2 = temp2->next;
        }
        return temp1;
    }
    static ListNode* temp1;
    static ListNode* temp2;
};
ListNode* Solution::temp1;
ListNode* Solution::temp2;

复杂度分析

时间复杂度： O(m+n)。同解法一。
空间复杂度： O(1)。只需要两个指针。