本文详解暴力解法的时间复杂度（o(m×n)）与空间复杂度（o(1)），并对比更优的双指针算法（o(m+n)/o(1)），附可运行代码与关键注意事项。
本文详解暴力解法的时间复杂度（o(m×n)）与空间复杂度（o(1)），并对比更优的双指针算法（o(m+n)/o(1)），附可运行代码与关键注意事项。
在链表相交问题中，“第一个相交节点”指的是两个单链表在内存中首次共享的同一物理节点（而非值相等的节点）。判断是否相交、并准确定位首个公共节点，是面试与系统设计中的经典问题。
你提供的实现采用嵌套遍历法：对链表1的每个节点，遍历整个链表2进行地址比对（currentPtr1 == currentPtr2）。该逻辑正确，但效率较低：
public Node getFirstNodeWhichIntersects(Node node1, Node node2) {
Node currentPtr1 = node1;
while (currentPtr1 != null) {
Node currentPtr2 = node2; // 每次内层循环重置起点
while (currentPtr2 != null) {
if (currentPtr1 == currentPtr2) {
return currentPtr1; // 找到首个地址相同的节点，立即返回
}
currentPtr2 = currentPtr2.next;
}
currentPtr1 = currentPtr1.next;
}
return null;
}
✅ 时间复杂度：O(m × n)
其中 m 和 n 分别为两链表长度。最坏情况下（如仅尾节点相交），需检查全部 m × n 对节点组合，无法提前剪枝。
✅ 空间复杂度：O(1)
仅使用 currentPtr1、currentPtr2、firstNode（未实际使用，可删）三个局部变量，无递归或额外数据结构，空间开销恒定。
⚠️ 关键注意事项：
- 此解法依赖引用相等性（==），而非 equals() 或值比较——这是判断“真正相交”的前提；
- 若链表无环且不相交，算法会完整遍历后返回 null，行为正确；
- 但面对长链表（如各10⁴节点），O(10⁸)操作将显著超时，生产环境不可取。
? 进阶优化：双指针法（推荐）
利用“走完本链表再走对方链表”的思想，使两指针在第二轮同步抵达交点（或同时为 null）：
public Node getIntersectionNode(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表示不相交
}
⏱ 时间复杂度：O(m + n)，每个指针最多遍历两链表一次；
? 空间复杂度：仍为 O(1)，仅用两个指针。
? 总结：暴力法逻辑直观、空间极致精简，但时间代价过高；双指针法在保持 O(1) 空间的同时，将时间优化至线性级别，是工程实践与算法面试的标准解法。务必理解其核心思想——构造等长路径消除长度差。
