题目
判断两条链表是否相交，如果相交则返回相交的第一个节点，否则返回 null。
这里的”相交”指的是同一个节点对象（引用相等），而不是节点值相等。
示例：
相交情况：
A: a1 → a2 → a3
↘
c1 → c2 → c3 → null
↗
B: b1 → b2
交点：c1（同一个节点引用）不相交情况：
A: a1 → a2 → a3 → null
B: b1 → b2 → null解题思路
使用双指针换头法，核心思想是：让两个指针分别走完 A+B 和 B+A 的总路程，因为总长度相等，它们会在交点相遇。
算法原理
假设：
- 链表 A 长度为
a，独有部分长度为x - 链表 B 长度为
b，独有部分长度为y - 公共部分长度为
c
则有：a = x + c，b = y + c
- 指针 p1 走的路程：
x + c + y（走完 A 再走 B 的独有部分） - 指针 p2 走的路程：
y + c + x（走完 B 再走 A 的独有部分）
因为 x + c + y = y + c + x，两个指针会同时到达交点 c 的起始位置。
如果不相交（c = 0），两个指针最终都会同时到达 null。
代码实现
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// p1: 遍历链表 A，遍历完 A 后继续遍历 B
// p2: 遍历链表 B，遍历完 B 后继续遍历 A
ListNode p1 = headA;
ListNode p2 = headB;
while (p1 != p2) {
// p1 走完 A 换到 B，继续走
if (p1 == null) {
p1 = headB;
} else {
p1 = p1.next;
}
// p2 走完 B 换到 A，继续走
if (p2 == null) {
p2 = headA;
} else {
p2 = p2.next;
}
}
// 返回相交节点；若不相交，最终 p1==p2==null
return p1;
}
}代码解释
- 初始化双指针：p1 从 headA 开始，p2 从 headB 开始
- 循环条件：
p1 != p2，直到两个指针相遇 - 指针移动逻辑：
- 如果指针为 null，说明走完了当前链表，切换到另一条链表的头部
- 否则继续向后移动
- 返回结果：
- 相交：返回交点节点
- 不相交：返回 null（因为两个指针最终都会到达 null）
执行过程示例
假设 A 长度 5，B 长度 3，公共部分长度 2：
A: a1 → a2 → a3 → c1 → c2
B: b1 → c1 → c2
p1 路径: a1 → a2 → a3 → c1 → c2 → null → b1 → c1
p2 路径: b1 → c1 → c2 → null → a1 → a2 → a3 → c1
在 c1 处相遇速记
双指针换头走，p1 走 A+B，p2 走 B+A，路程相等必在交点相遇，无交点则同时到 null。
注意点
- 判断相交用引用相等：用
==比较节点对象，不是比较值 - 换头时机：指针为 null 时换到另一条链表，不是到达 null 前的最后一个节点
- 循环终止条件：
p1 != p2，不需要额外的计数器 - 特殊情况处理：
- 两个链表都为空：第一次循环 p1 == p2 == null，直接返回 null
- 一个为空一个不为空：也能正确处理，最终都会到达 null
复杂度分析
- 时间复杂度：O(m + n)，每个指针最多遍历两条链表的总长度
- 空间复杂度：O(1)，只使用了两个指针变量