160. 相交链表#

生活中的相遇问题#

想象两个人从不同的地方出发，最后在一个十字路口相遇。他们可能走过不同长度的路程，但最终会在同一个点汇合。这就很像我们今天要讨论的相交链表问题：两个链表从不同的起点出发，在某个节点相交，然后共享后续的路径。

问题描述#

题目目标#

给你两个单链表的头节点 headA 和 headB，请找出并返回它们相交的起始节点；如果两个链表没有相交，则返回 null。

示例 1#

输入： 两个链表在节点 c1 处相交。 输出： 返回节点 c1 链表示意：

A: a1 -> a2
            \
             c1 -> c2 -> c3 -> null
            /
B: b1 -> b2 -> b3

text

说明： 从节点 c1 开始，两个链表共享同一段尾部，因此相交起点就是 c1。

补充说明#

判断“相交”看的是节点地址是否相同，而不是节点值是否相同。
相交后，两个链表后续的所有节点都会完全共享。

最直观的解法：哈希表记录#

就像在一个城市里标记每个人走过的地方，最简单的方法是用一个哈希表记录第一个人走过的所有位置，然后看第二个人的路径中是否有重复的地方。

哈希表方法的实现#

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // visited：哈希集合，用来记录链表A中“访问过的节点对象（按地址）”
        Set<ListNode> visited = new HashSet<>();

        // current：当前遍历指针，先从链表A头节点开始扫描
        ListNode current = headA;
        while (current != null) {
            // 将当前节点加入集合，后续可 O(1) 判断链表B节点是否与之重合
            visited.add(current);
            // 指针后移，继续遍历链表A
            current = current.next;
        }

        // 重新让 current 指向链表B头节点，开始扫描链表B
        current = headB;
        while (current != null) {
            // 如果当前B节点已在A的集合中，说明两个链表在该节点首次相交
            if (visited.contains(current)) {
                // 返回相交起点（注意比较的是节点地址，不是节点值）
                return current;
            }
            // 否则继续向后找
            current = current.next;
        }

        // 扫描完B仍未命中，说明两个链表不相交
        return null;
    }
}

java

优化解法：双指针技巧#

仔细思考，我们发现一个有趣的现象：如果两个人分别走对方的路，他们最终一定会相遇！这就是双指针解法的灵感来源。

双指针方法的原理#

想象两个人在散步：

A从链表A出发，走完后转到链表B继续走
B从链表B出发，走完后转到链表A继续走
如果链表相交，他们一定会在相交点相遇
- 因为他们走过的总路程是相同的：链表A长度 + 链表B长度

示例运行#

假设链表A：1→2→3→4，链表B：5→6→3→4（3是相交点）

指针A：1 → 2 → 3 → 4 → 5 → 6 → [3] ← 相遇！
指针B：5 → 6 → 3 → 4 → 1 → 2 → [3] ← 相遇！

plaintext

Java代码实现#

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 边界处理：任意一个链表为空，都不可能相交
        if (headA == null || headB == null) {
            return null;
        }

        // pointerA：先走链表A；pointerB：先走链表B
        // 两者最终都会走过 A+B 的总长度
        ListNode pointerA = headA;
        ListNode pointerB = headB;

        // 当两个指针指向不同节点时持续前进
        // 若相交会在交点相遇；若不相交会同时变为 null
        while (pointerA != pointerB) {
            // pointerA 走到末尾后切换到链表B头，实现“补齐路径差”
            pointerA = (pointerA == null) ? headB : pointerA.next;
            // pointerB 走到末尾后切换到链表A头，同理补齐路径差
            pointerB = (pointerB == null) ? headA : pointerB.next;
        }

        // 循环结束时两者相等：
        // 1) 相交：相等点即交点
        // 2) 不相交：两者都为 null
        return pointerA;
    }
}

java

解法比较#

让我们比较这两种方法：

哈希表法：

时间复杂度：O(m+n)
空间复杂度：O(m)，m为链表A的长度
优点：思路直观，容易理解
缺点：需要额外的空间存储节点

双指针法：

时间复杂度：O(m+n)
空间复杂度：O(1)
优点：不需要额外空间，优雅简洁
缺点：理解起来稍微有点难度

实用技巧总结#

解决链表相交问题的关键点：

理解相交后的节点都是共享的
考虑特殊情况（如空链表、不相交的情况）
善用双指针技巧
利用数学特性（路程相等原理）

小结#

通过相交链表这道题，我们学会了如何巧妙地使用双指针技巧来解决看似复杂的问题。这种思维方式不仅能解决算法题，在处理数据流、文件比较等实际问题时也很有用。记住，当遇到需要找到两个序列共同元素的问题时，双指针技巧往往能提供一个优雅的解决方案！

延伸思考：

如果链表可能有环，这个算法还有效吗？
如果要找到所有的相交节点，应该如何修改算法？
在分布式系统中，如何处理类似的”路径相交”问题？