题目

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

题目数据 保障 整个链式构造中不存在环。
留神，函数返回后果后，链表必须 放弃其原始构造。

输出：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输入：Intersected at '8'
解释：相交节点的值为 8（留神，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

哈希表

最简略的思路，遍历链表 A，把每个节点存在一个字典 (hash 表) 中。
再遍历字典 B，看 B 的以后节点是否在字典中，存在的话就是相交节点。

双指针

定义两个指针 A,B，别离从各自的链表表头开始遍历，
如果两个指针指向的节点不同，就持续向后挪动
如果两个指针指向的节点雷同，则找到了相交节点，包含两个不相交的链表，两个指针最终都会挪动到尾部节点指向的 None，则也会返回 None
当某个指针挪动到链表开端时，跳转到另一个链表的表头开始遍历，这样做能保障两个不对称的相交链表，通过指针挪动，最终总能同时挪动到相交节点上

def getIntersectionNode(headA,headB):
    if not headA or not headB:
        return None

    A,B = headA,headB
    while A!=B:
        A = A.next if A else headB
        B = B.next if B else headA
    return A