本文详解暴力法求两单链表首个相交节点的时间与空间复杂度，并对比更优的双指针算法，指出其 o(m×n) 时间开销与 o(1) 空间优势，同时提供优化方案与可运行代码。
本文详解暴力法求两单链表首个相交节点的时间与空间复杂度，并对比更优的双指针算法，指出其 o(m×n) 时间开销与 o(1) 空间优势，同时提供优化方案与可运行代码。
该方法采用嵌套遍历策略：对链表1中每个节点，遍历整个链表2，逐一对比引用是否相等（注意：此处判断的是内存地址相同，即是否为同一物理节点，而非值相等）。一旦发现 currentPtr1 == currentPtr2，立即返回该节点——这正是首个相交节点（因按链表1顺序扫描，首次命中即为“第一个”）。
时间复杂度分析：
外层循环执行 m 次（m 为链表1长度），内层循环在最坏情况下每次都执行 n 次（n 为链表2长度），例如两链表仅在尾部共享最后一个节点。因此总比较次数为 m × n，时间复杂度为 O(m × n)。这是典型的平方级开销，在长链表场景下性能显著劣化。
空间复杂度分析：
函数仅使用 currentPtr1、currentPtr2 和 firstNode 三个局部变量，不依赖输入规模，无递归调用或额外数据结构，故空间复杂度为严格的 O(1)。
⚠️ 注意事项：
- 此算法假设“相交”意味着两链表共享同一段后缀（即从某节点起完全共用后续所有节点），这是单链表相交的标准定义；
- 仅比较节点引用（==），绝不可用 equals() 或值比较，否则逻辑错误；
- 若链表无环且不相交，最终返回 null，符合预期。
✅ 更优解：双指针法（推荐）
利用“走过相同路径长度必相遇”的思想，将时间复杂度降至 O(m + n)，空间仍为 O(1)：
public Node getFirstIntersectingNode(Node headA, Node headB) {
if (headA == null || headB == null) return null;
Node ptrA = headA, ptrB = headB;
while (ptrA != ptrB) {
ptrA = (ptrA == null) ? headB : ptrA.next;
ptrB = (ptrB == null) ? headA : ptrB.next;
}
return ptrA; // 相交则为交点，不相交则为 null
}
该算法让两指针分别遍历自身链表后跳转至对方头节点，总步数恒为 m + n，确保在第二次遍历时同步抵达交点（或同时为 null）。它简洁、高效，是面试与工程实践中的标准解法。
综上，原始嵌套循环法虽逻辑直观，但时间效率低下；掌握并应用双指针法，方能在保证常数空间的同时实现线性时间最优解。
