1 题目
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
注意：
如果两个链表没有交点，返回 null。
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
2 图解
考虑构建两个节点指针 A? , B 分别指向两链表头节点 headA , headB ，做如下操作：
指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为：
a + (b - c)
a+(b?c)
指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为：
b + (a - c)
b+(a?c)
如下式所示，此时指针 A , B 重合，并有两种情况：
a + (b - c) = b + (a - c)
a+(b?c)=b+(a?c)
若两链表 有 公共尾部 (即 c > 0c>0 ) ：指针 A , B 同时指向「第一个公共节点」node 。
若两链表 无 公共尾部 (即 c = 0c=0 ) ：指针 A , B 同时指向 nullnull 。
因此返回 A 即可。
如下图所示，为 a = 5a=5 , b = 3b=3 , c = 2c=2 示例的算法执行过程。
思路来源链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/solution/intersection-of-two-linked-lists-shuang-zhi-zhen-l/
（1）第一步
（2）第二步
（3）第三步
（4）第四步
B走到了null，则指针接下来将会指向HeadA
（5）第五步
B指针指向HeadA
（6）第六步
A走到了null，则指针接下来将会指向HeadB
（7）第七步
（8）第八步
指针A等于指针B，此时返回指针A即可。如果两条链没有相交，一定会在Null相交，返回的是NULL
3 Python实现
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
'''
方法一：双指针法，图解参考https://leetcode.cn/problems/intersection-of-two-linked-lists/solution/intersection-of-two-linked-lists-shuang-zhi-zhen-l/
时间复杂度：O(m+n)O(m+n)，其中 mm 和 nn 是分别是链表 \textit{headA}headA 和 \textit{headB}headB 的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次。
空间复杂度：O(1)O(1)。
'''
A,B = headA,headB
while(A!=B):
A = A.next if A else headB
B = B.next if B else headA
return A
注意以上代码的用法
A if case else B表示如果case为真，则返回 A，否则返回 B。
