题目链接：https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
image.png
题目解析：
本题目采用双指针的方式，当A B指针不相等的时候，依次遍历，如果A B指针任意为null，就赋值A=B(如果A为null)或者B=A(如果B为null)
原理: A的长度为a，B的长度为b, 相交点距离最末尾的距离为c 。那么A从头走到尾，在从B的头走到相交点，那么距离就是a+(b-c)；B从头走到尾，在从A的头走到相交点，那么距离是b+(a-c)，满足加法交换律，所以找到相交点。
图文分析可见：https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/solution/jian-zhi-offer-52-liang-ge-lian-biao-de-gcruu/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode A = headA,B = headB;
while (A != B){
A = A == null ? headB : A.next;
B = B == null ? headA : B.next;
}
return headA;
}
复杂度分析
空间复杂度: O(1)。
时间复杂度: O(M+N)。
网友评论