LeetCode 补充题 119. 链表相交判定（允许有环）
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 160. 相交链表
:::
给你两条单链表的头节点，两条链表都可能存在环。请判断它们是否共享至少一个节点，并返回布尔值。
是否相交按节点身份判断，而不是按节点值判断。不能修改任何节点的
next指针。
示例 1：
输入：
环为节点 A→B→C→A，第一条链表表头为 A，第二条链表表头为 B
输出：true
解释： 两条链表共享同一组节点，进入环的位置不同仍属于相交。
示例 2：
输入：
第一条链表为 A→B→A；第二条为 C→D→null，四个节点互不相同
输出：false
解释： 若存在共享节点，第二条链表也会沿共享后缀进入环，与无环条件矛盾。
提示：
- 按节点身份判断相交，而不是节点值。
- 链表允许有环。
- 返回布尔值。
- 不能修改任何
next指针。
题意分析
若直接遍历到空指针，有环链表会无法结束。先分别判断是否有环并定位入口，再讨论两条链表的组合情况。这里仅返回是否共享节点，不必寻找唯一的第一个交点。
解法：按两个环入口分类判断相交
核心思路
[!blue]
求入口时使用 Floyd：慢指针每次走一步，快指针走两步；快指针遇空表示无环，相遇则表示有环。设入环前长度为
a、环长为c、相遇点距入口为b，快慢路程差是环长的整数倍，因此a + b是c的倍数。把一个指针放回表头、两者同步走一步，就会在入口相遇。两条链都无环时，双指针到尾后切换到另一条表头，消去长度差；有交点则在共享后缀相遇，否则同时为空。只有一条有环时不可能相交，因为共享节点之后的
next唯一，无环链也会因此入环。两条都有环时，从第一个入口完整绕环一周，检查能否遇到第二个入口。遇到说明共享同一个环，入口相同或不同都返回 true；否则属于两个独立环，返回 false。整个过程中比较节点身份，不比较节点值，也不改写连接。
解题步骤
- 分别用 Floyd 求两条链的环入口。
- 都无环时使用换头双指针，恰有一条有环时返回 false。
- 都有环时，从第一入口沿环走一圈，检查是否包含第二入口。
代码实现
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
class Solution {
private ListNode entry(ListNode head) {
ListNode slow = head;
ListNode fast = head;
do {
if (fast == null || fast.next == null) {
return null;
}
slow = slow.next;
fast = fast.next.next;
} while (slow != fast);
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
public boolean intersects(ListNode a, ListNode b) {
ListNode x = entry(a);
ListNode y = entry(b);
if (x == null && y == null) {
ListNode p = a;
ListNode q = b;
while (p != q) {
p = p == null ? b : p.next;
q = q == null ? a : q.next;
}
return p != null;
}
if (x == null || y == null) {
return false;
}
ListNode p = x;
do {
if (p == y) {
return true;
}
p = p.next;
} while (p != x);
return false;
}
}
type ListNode struct {
Val int
Next *ListNode
}
func cycleEntry(head *ListNode) *ListNode {
slow, fast := head, head
for {
if fast == nil || fast.Next == nil {
return nil
}
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
break
}
}
slow = head
for slow != fast {
slow = slow.Next
fast = fast.Next
}
return slow
}
func intersects(a, b *ListNode) bool {
x, y := cycleEntry(a), cycleEntry(b)
if x == nil && y == nil {
p, q := a, b
for p != q {
if p == nil {
p = b
} else {
p = p.Next
}
if q == nil {
q = a
} else {
q = q.Next
}
}
return p != nil
}
if x == nil || y == nil {
return false
}
p := x
for {
if p == y {
return true
}
p = p.Next
if p == x {
break
}
}
return false
}
复杂度分析
- 时间复杂度：$O(n+m)$。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
只返回相交与否，所以两条有环链共享同一环就足够；无需再选出唯一的首次交点。
易错点总结
[!yellow]
比较节点引用而非节点值；共用一个环但入口不同，也属于相交。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 160. 相交链表 | 简单 | 无环分支直接复用换头双指针；有环时不能靠到达 null 结束，需先分类。 |
| 142. 环形链表 II | 中等 | 环入口是分类依据；两个入口不同仍可能处于同一个环，不能据此直接否定相交。 |