E160.相交链表

hash table, linked list, two pinters, https://leetcode.cn/problems/intersection-of-two-linked-lists/

思路：一路存地址即可，用时约20min

class Solution 
{
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) 
	{
        map<ListNode*, int> m;
		while (headA != NULL)
		{
            m[headA] = 1;
            headA = headA->next;

		}
		while (headB != NULL)
		{
            if (m.find(headB) != m.end())
                return headB;
            headB = headB->next;
		}
        return NULL;

    }
};

/**
 * 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_set<ListNode *> visited;
        ListNode *temp = headA;
        while (temp != nullptr) {
            visited.insert(temp);
            temp = temp->next;
        }
        temp = headB;
        while (temp != nullptr) {
            if (visited.count(temp)) {
                return temp;
            }
            temp = temp->next;
        }
        return nullptr;
    }
};