How

第一遍遍历a，如果用一个hashset存储所有node，第二遍遍历b，检查node是否在hashset里面，但是需要额外的空间O(m + n)

如果不用额外的空间，可以思考遍历的node数量关系，如果diff = m - n，长的链表先移动diff，再一起开始遍历相同次数，当node相等时，可以找到交叉点。比较长短之后，需要分两种情况，代码较长

如果两个链表都遍历，则最多需要遍历m + n，并且两个链表尾部一定相等，可以倒推相同个node到相交点，假设尾部有x个node，可以得出在遍历到m + n - x的地方相遇

相当于每个路线都走了一个Y字型路线，路线长度相等，且在分叉处相遇

Code

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        node1, node2 = headA, headB
        while node1 != node2:
            node1 = node1.next if node1 else headB
            node2 = node2.next if node2 else headA

        return node1

Complexity

Time $O(m+n)$

Space $O(1)$