【LeetCode HOT100】160. 相交链表

题目 ​

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

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须保持其原始结构。

自定义评测：

评测系统的输入如下（你设计的程序不适用此输入）：

• intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
• listA - 第一个链表
• listB - 第二个链表
• skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
• skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被视作正确答案。

提示 ​

一句话思路：两个指针各自走完自己的链表后，接着去走对方的链表——走过相同总长度，最终一定在交点（或 null）相遇。

设第一个公共节点为 node，headA 共有 a 个节点，headB 共有 b 个节点，公共尾部有 c 个节点：

• 指针 A 从 headA 出发，走完 A 再走 B，走到 node 时共走 a + (b - c) 步；
• 指针 B 从 headB 出发，走完 B 再走 A，走到 node 时共走 b + (a - c) 步。

两者相等，所以 A、B 必在交点相遇：

• 有公共尾部（c > 0）：同时指向第一个公共节点 node；
• 无公共尾部（c = 0）：同时指向 null。

因此返回 A 即可。时间复杂度 O(a + b)，空间 O(1)。

答案 ​

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        A = headA               # 指针 A 从 headA 出发
        B = headB               # 指针 B 从 headB 出发
        while A != B:           # 未相遇就继续走
            A = A.next if A else headB      # A 走完自己的链表后，换到 headB 继续走
            B = B.next if B else headA      # B 走完自己的链表后，换到 headA 继续走
        return A                # 相遇点即相交节点；不相交时两者同时为 null，返回 null