问题说明（含示例）

问题描述：给定两个单链表的头节点 headA 和 headB，找出并返回两个链表相交的起始节点。若两个链表不存在相交节点，返回 null。关键注意：链表相交的定义是 “节点在内存中指向同一位置”（即地址相同），而非 “节点值相同”；且函数返回后需保持链表原始结构，整个链式结构中不存在环。

示例：

1. 输入：intersectVal = 8，listA = [4,1,8,4,5]，listB = [5,6,1,8,4,5]，skipA = 2，skipB = 3输出：Intersected at '8'解释：

   • 链表 A 的结构为 4 → 1 → 8 → 4 → 5，链表 B 的结构为 5 → 6 → 1 → 8 → 4 → 5；
   • 相交起始节点为值为 8 的节点（内存地址相同），A 中该节点前有 2 个节点，B 中前有 3 个节点；
   • 注意：A 中值为 1 的节点与 B 中值为 1 的节点地址不同，不属于相交节点。

2. 输入：intersectVal = 2，listA = [1,9,1,2,4]，listB = [3,2,4]，skipA = 3，skipB = 1输出：Intersected at '2'解释：相交起始节点为值为 2 的节点，A 中该节点前有 3 个节点，B 中前有 1 个节点。

3. 输入：intersectVal = 0，listA = [2,6,4]，listB = [1,5]，skipA = 3，skipB = 2输出：No intersection解释：两个链表无相交节点，故返回 null。

解题关键

最优解法为 双指针法，核心思路是通过 “交叉遍历” 让两个指针最终在相交节点相遇（或同时到达链表末尾），空间复杂度仅为 O(1)，具体逻辑如下：

1. 指针初始化：定义两个指针 pA 和 pB，分别从 headA 和 headB 出发。
2. 交叉遍历规则：
   • 当 pA 遍历完链表 A（到达 null），立即将其指向 headB，继续遍历；
   • 当 pB 遍历完链表 B（到达 null），立即将其指向 headA，继续遍历；
3. 相遇条件：
   • 若两链表相交：pA 和 pB 会在遍历 a + c + b 步（或 b + c + a 步）后，同时到达相交节点（a 为 A 的非相交长度，b 为 B 的非相交长度，c 为相交长度）；
   • 若两链表不相交：pA 和 pB 会在遍历 a + b 步后，同时到达 null。

对应源码

from typing import Optional

# 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) -> Optional[ListNode]:
        # 初始化双指针，分别指向两个链表的头节点
        pA, pB = headA, headB
        
        # 循环直到两个指针相遇（或同时为null）
        while pA != pB:
            # pA遍历完A则跳向B的头，否则继续往后走
            pA = pA.next if pA else headB
            # pB遍历完B则跳向A的头，否则继续往后走
            pB = pB.next if pB else headA
        
        # 若相交，pA/pB为相交节点；若不相交，pA/pB均为null
        return pA

对应的基础知识

实现该算法需掌握以下单链表与指针操作的基础知识点：

1. 单链表的结构与访问

   • 单链表由 ListNode 节点组成，每个节点包含 val（节点值）和 next（指向后续节点的指针，初始为 null）；
   • 链表只能从头部（head）开始向后遍历，无法直接回溯（无前驱指针），需通过 node.next 访问下一个节点。

2. 双指针的初始化与移动

   • 定义两个指针 pA 和 pB，初始分别指向 headA 和 headB，确保从链表起点同步出发；
   • 指针移动逻辑：pA.next if pA else headB 表示 “若当前指针未到链表末尾，则向后走一步；否则跳向另一个链表的头部”，避免指针 “停滞”。

3. 循环条件的设计

   • 循环终止条件为 pA == pB，包含两种情况：
     • 两链表相交：pA 和 pB 同时指向相交节点；
     • 两链表不相交：pA 和 pB 同时指向 null（遍历完所有节点后）。

4. Optional 类型的理解

   • 返回类型 Optional[ListNode] 表示函数可能返回 ListNode 实例（相交节点），也可能返回 None（不相交），符合 Python 的类型提示规范。

对应的进阶知识

该问题的解决涉及链表遍历优化与复杂度分析的进阶思想：

1. 双指针法的数学原理假设链表 A 的非相交长度为 a，相交长度为 c；链表 B 的非相交长度为 b，相交长度为 c。

   • pA 遍历路径：a → c → b（总长度 a + c + b）；
   • pB 遍历路径：b → c → a（总长度 b + c + a）；由于 a + c + b = b + c + a，两指针会在相同步数后相遇（相交节点或 null），无需计算链表长度即可实现对齐。

2. 复杂度对比（双指针法 vs 哈希表法）

   • 双指针法：时间复杂度 O(m + n)（m、n 分别为 A、B 的长度，两指针最多遍历 m + n 步），空间复杂度 O(1)（仅用两个指针，无额外存储）；
   • 哈希表法：需先遍历 A，将所有节点存入哈希表（空间 O(m) 或 O(n)），再遍历 B 查询节点是否在哈希表中（时间 O(m + n)）；双指针法在空间效率上更优，尤其适合大规模链表（如 m/n 达 3×10^4）。

3. 边界情况的隐性处理

   • 链表为空？题目提示 1 ≤ m, n ≤ 3×10^4，无需处理空链表；
   • 其中一个链表完全包含另一个？例如 A 为 1→2→3，B 为 2→3，双指针仍会相遇（pA 遍历 1→2→3→null→2，pB 遍历 2→3→null→1→2，在 2 相遇）；
   • 无相交节点？两指针最终同时到达 null，返回 null，无需额外判断。

4. 链表遍历的 “不可回溯” 特性适配单链表无法直接获取尾节点或长度，双指针的 “交叉跳转” 巧妙规避了 “需先计算长度再对齐” 的步骤（如先算 lenA - lenB，让长链表指针先跳 |lenA - lenB| 步），代码更简洁且无需额外遍历求长度。