hot100 打开链表的另一种方式

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

题为leetcode160
思路：

第一种，用哈希表，先遍历A链表，将所有节点指针存入哈希表，然后遍历B链表，有一样的指针返回该指针，否则返回nullptr。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *A=headA;
        unordered_set<ListNode *> visited;
        while(A!=nullptr){
            visited.insert(A);
            A=A->next;
        }
        A=headB;
        while(A!=nullptr){
            if(visited.count(A))return A;
            A=A->next;
        }
        return nullptr;

    }
};

第二种： 

步骤：

1. 每步操作需要同时更新指针 A 和 B。
2. 如果指针 A 不为空，则将指针A 移到下一个节点；如果指针 B 不为空，则将指针 B 移到下一个节点。
3. 如果指针 A 为空，则将指针 A 移到链表 headB 的头节点；如果指针B 为空，则将指针 B 移到链表 headA 的头节点。
4. 当指针 A 和 B 指向同一个节点或者都为空时，返回它们指向的节点或者 null

结合上面步骤演示一遍，题解很妙借鉴leetcode官方，也可以看下图，最终都指向了同一节点。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *A,*B;
        if(headA==nullptr||headB==nullptr)return nullptr;
        A=headA,B=headB;
        while(A!=B){
            A=A==nullptr?headB:A->next;
            B=B==nullptr?headA:B->next;
        }
        return A;
    }
};