如何判断两个单链表是否相交？如何找到相交的起点？

简化版

两个链表相交后会共用后半段（Y 字形），所以尾节点一定相同——用这个可判断是否相交。找交点最优雅的办法是双指针接力：指针 A 走完链表 a 接着走链表 b，指针 B 走完 b 接着走 a，两者走的总长度相等（la+lb），会在交点相遇；若不相交，则同时走到 null。O(m+n) 时间、O(1) 空间。

详细版

两个单链表相交是「Y 字形」：从某个节点起完全重合，共用尾部（不可能是 X 形交叉，因为单链表每个节点只有一个 next，一旦相交就再也分不开）。

判断是否相交：分别走到两个链表的尾节点，若尾节点是同一个对象（引用相等），则相交。

找交点——双指针接力法：

ListNode getIntersection(ListNode a, ListNode b) {
    if (a == null || b == null) return null;
    ListNode pa = a, pb = b;
    while (pa != pb) {
        pa = (pa == null) ? b : pa.next;  // a 走完转到 b 头
        pb = (pb == null) ? a : pb.next;  // b 走完转到 a 头
    }
    return pa;   // 相遇点即交点；不相交则同时为 null
}

若相交：pa 走 la + (lb - c)、pb 走 lb + (la - c)（c 是公共长度），两者相等，必在交点相遇。
若不相交：各走 la + lb 步后同时变 null，循环结束返回 null。

完整版教学

一、为什么相交必是 Y 形、尾部必相同

单链表每个节点只有一个 next。一旦链表 a 的某个节点和链表 b 的某个节点是同一个，那从这个节点往后，两条链走的是完全同一串节点（因为 next 唯一），直到同一个尾节点。所以相交后不会再分叉，形状是 Y（共用尾巴），且两链表的尾节点必是同一个对象。这就给了最简单的判断法：比较尾节点。

注意判断相交要比较节点引用（是不是同一个对象），不是比较节点的值——值相同不代表是同一个节点。

二、双指针接力法为什么能对齐到交点

难点在于两个链表长度不同，直接同时往后走不会在交点相遇（长的那条先到交点、短的还没到）。接力法的巧思是让两个指针走的总路程相等：

pa 的路径：a 全长 + b 中交点前的部分。
pb 的路径：b 全长 + a 中交点前的部分。

两条路径长度都是 la + lb - c（c 为公共段长度），所以它们同步到达交点。相当于用「换到对方起点接着走」抹平了长度差。

三、若不相交会怎样

如果两链表不相交，接力后 pa 走 la + lb、pb 走 lb + la，步数相同，会同时走到各自的 null。此时 pa == pb == null，循环条件 pa != pb 不成立，退出，返回 null。所以这套代码天然覆盖了「不相交」的情况，不用特判。

四、其他解法对比

哈希集合法：遍历 a 把所有节点存进 HashSet，再遍历 b，第一个在集合里出现的节点就是交点。O(m+n) 时间但 O(m) 空间。
长度差对齐法：先算两链表长度差 d，让长的先走 d 步，然后两指针一起走，相遇即交点。O(m+n) 时间、O(1) 空间，思路直观但要先遍历求长度。
双指针接力法：O(1) 空间且代码最短，是首选。

五、易错点

比较的是节点身份（引用），不是值。
循环条件用 pa != pb，让「不相交时同时为 null」自然结束，别写成 pa != null && pb != null（那样不相交时会死循环或漏判）。
空链表要先判 null。

六、常见误区与追问

解法	时间复杂度	空间复杂度	面试评价
哈希集合	O(m+n)	O(m)	直观但空间不优
长度差对齐	O(m+n)	O(1)	清晰，需要先算长度
双指针接力	O(m+n)	O(1)	代码最短，标准优解

易错点：链表相交比较的是“同一个节点对象”，不是节点值相等。两个值都为 7 的节点，可能完全不是同一个节点。

带数字理解接力法：链表 A 独有长度 3，链表 B 独有长度 5，公共尾部长度 2。pa 先走 A 再走 B，到交点前路程是 3 + 2 + 5 = 10 中的前 8 步；pb 先走 B 再走 A，到交点前也是 5 + 2 + 3 = 10 中的前 8 步。交换起点后，两者把长度差抵消，就会同步到达交点。

误区：节点值相同就说明两个链表相交。 相交要求引用相同，值相同只是数据相等。
误区：两个链表相交后还可能再次分开。 单链表每个节点只有一个 next，一旦共用节点，后续尾部必然完全相同。
误区：双指针接力法需要提前知道长度差。 它通过走完后切换到对方头节点，自动把长度差抹平。
追问：不相交时会不会死循环？ 不会，两个指针都走 la + lb 后同时为 null，循环自然结束。
追问：为什么尾节点相同能判断相交？ 因为相交后尾部共用，最终尾节点必然是同一个对象。
追问：如果链表本身有环怎么办？ 这题默认无环；若有环，需要先判环，再按入口和环内关系分类处理，不能直接套无环接力法。

七、加强记忆

两单链表相交必是 Y 形、共用尾部、尾节点是同一对象（因为 next 唯一）。找交点用双指针接力：pa 走完 a 转 b、pb 走完 b 转 a，两者路程都是 la+lb-c，同步在交点相遇；不相交则同时到 null。O(m+n) 时间、O(1) 空间。比较的是节点引用不是值。

简化版

详细版