160.相交链表

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

• 思路:

  • 本题中，交点不是数值相等，而是指针相等

  • 双指针遍历两遍后必定相遇，因为它们走过的路径长度相同，最终会在交点相遇

  • 推导:

    假设:：链表 A 长度为 m，即 headA 到 null 的长度。链表 B 长度为 n，即 headB 到 null 的长度。相交部分长度为 c，即交点 intersectNode 到 null 的长度

    headA 到交点的距离为 a，即 m = a + c
    headB 到交点的距离为 b，即 n = b + c

    用等式表示为：

    链表 A 的路径： a + c
    链表 B 的路径： b + c

    • 双指针走的路径
      假设 pointerA 从 headA 开始，pointerB 从 headB 开始：

      第一轮遍历

      pointerA 走过 m（即 a + c）步后到达 null，然后跳到 headB
      pointerB 走过 n（即 b + c）步后到达 null，然后跳到 headA

      第二轮遍历

      pointerA 继续从 headB 走 b 步，此时已到达交点
      pointerB 继续从 headA 走 a 步，此时已到达交点

      也就是说，两个指针在同时走过 a + b + c 步时，同时到达相交点，最终两个指针走过的总步数都是：m + n = (a + c) + (b + c) = a + b + 2c

      由于两者的步数完全相同，它们一定会在第二轮遍历的 c 步处相遇，也就是相交点，反之如果遍历两边后两指针都不相遇，说明不存在交点

  -

def getIntersectionNode(headA, headB):
    # 如果链表 A 或者链表 B 为空，直接返回 null
    if not headA or not headB:
        return None
    
    # 初始化两个指针
    pointerA = headA
    pointerB = headB
    
    # 当两个指针没有相遇，且都没有遍历完两个链表时
    while pointerA != pointerB:
        # 指针 A 遍历完后指向链表 B 的头部，指针 B 遍历完后指向链表 A 的头部
        pointerA = pointerA.next if pointerA else headB
        pointerB = pointerB.next if pointerB else headA
    
    return pointerA  # 如果相交，返回相交的节点；如果没有相交，返回 None

• 时间复杂度: O(m+n)，每个指针最多只走 m + n 步
• 空间复杂度: O(1)