image.png

思路

双指针 想办法使得尾部对齐，然后就可以同步往后 如果出现俩个节点一致就是交点 如果最后都到了空 说明没交点

实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        A,B = headA,headB
        a_len,b_len=0,0
        while(A):
            A=A.next
            a_len+=1
        while(B):
            B=B.next
            b_len+=1
        diff = abs(a_len-b_len)
        for i in range(diff):
            headA=headA.next if a_len>b_len else headA
            headB=headB.next if b_len>a_len else headB
        while(headA and headB): # 对齐完第一个节点可能就相交了
            if headA==headB:
                return headA
            headA=headA.next
            headB=headB.next
        return None

优化

能不能不去遍历两遍链表，而是在同一个循环中解决问题呢？
可以！ 当指针跑到末尾之后时，我们让它等于另一个链表的头，为什么这是可行的？因为当一个指针走到末尾时，说明这个指针走过了这整个链表的长度,我们考虑原来走长链的指针，它到末尾时，短指针肯定已经重定位过了，此时短指针也走了长链表的长度，然后长指针被定位到短链表上,此时，恰好形成末尾对齐的情况，直接遍历即可，遇到相等的节点返回就好了。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        A,B=headA,headB
        while(A!=B):
            A=A.next if A else headB
            B=B.next if B else headA
        return A