给你两个单链表的头节点 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; } };
第二种：
步骤：
- 每步操作需要同时更新指针 A 和 B。
- 如果指针 A 不为空，则将指针A 移到下一个节点；如果指针 B 不为空，则将指针 B 移到下一个节点。
- 如果指针 A 为空，则将指针 A 移到链表 headB 的头节点；如果指针B 为空，则将指针 B 移到链表 headA 的头节点。
- 当指针 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; } };
