// 双指针算法
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == NULL || headB == NULL) {
            return NULL;
        }

        auto p1 = headA, p2 = headB;
        while(p1 != p2) {
            p1 = p1 == NULL ? headB : p1 = p1->next;
            p2 = p2 == NULL ? headA : p2 = p2->next; 
        }

        return p1;
    }
};

// 哈希集合
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 1. 处理特殊情况
        if (headA == NULL || headB == NULL) {
            return NULL;
        }

        // 2. 数组存储链表 A
        vector<ListNode*> v; 
        for (auto i = headA; i ; i = i->next) {
            v.push_back(i);
        }

        // 3. 遍历链表 B，并查找对应的指针
        for (auto i = headB; i; i = i->next) {
            if (find(v.begin(), v.end(), i) != v.end()) {
                return i;
            }
        }

        return NULL;
    }
};