单链表相交节点查找方法详解

本文深入剖析单链表寻找首个相交节点的经典问题，明确指出“相交”指两个链表共享同一物理内存节点（而非值相同），并对比了直观但低效的暴力嵌套遍历法（O(m×n)时间）与优雅高效的双指针法（O(m+n)时间、O(1)空间）；通过可运行代码和关键注意事项（如必须用==比较地址、避免值比较陷阱），揭示双指针法如何巧妙利用“走完本链再走对方链”来消除长度差异、实现线性时间精准定位，是面试必会、工程首选的最优解。

本文详解暴力解法的时间复杂度（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) 空间的同时，将时间优化至线性级别，是工程实践与算法面试的标准解法。务必理解其核心思想——构造等长路径消除长度差。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《单链表相交节点查找方法详解》文章吧，也可关注golang学习网公众号了解相关技术文章。