LeetCode 160. 相交链表
题目核心
给定两个单链表 headA 和 headB，判断它们是否相交。如果相交，返回第一个相交节点；如果不相交，返回 null。
这里的“相交”不是指节点值相等，而是指两个链表从某个节点开始共用同一段节点，也就是节点引用相同。
解题思考过程
第一步：理解问题
两个链表可能有不同的长度，如果它们相交，那么从相交点开始到末尾是共用的。
A: 1 -> 2 -> 3
\
4 -> 5 -> null
/
B: 6 ->长度：A=5, B=4，相交点是节点4。
第二步：暴力解法（哈希表）
最直接的思路：遍历链表A，把所有节点存入哈希表，然后遍历链表B，检查每个节点是否在哈希表中。
时间复杂度：O(m + n)
空间复杂度：O(m) 或 O(n)这个思路可行，但需要额外的哈希表空间。
第三步：思考如何优化空间
能不能不用额外空间？
想到：如果两个链表长度不同，长链表先走几步，然后两个指针一起走，相遇时就是交点。
A: 1 -> 2 -> 3 -> 4 -> 5 (长度5)
B: 6 -> 4 -> 5 (长度3)
长链表A先走 5-3=2 步：
A指针到3，B指针到6
然后一起走：
A: 3 -> 4
B: 6 -> 4
相遇！交点是4但这个方法需要先计算两个链表的长度，比较繁琐。
第四步：想到双指针切换法
有没有更巧妙的方法？
如果让两个指针都走完两个链表的总长度呢？
指针A：走A链表，走到头后走B链表
指针B：走B链表，走到头后走A链表
A: 1->2->3->4->5->null->6->4->5
B: 6->4->5->null->1->2->3->4->5
走了 5+4=9 步后，两个指针都到达交点4！为什么会相遇？
- 如果两个链表相交，交点之后的长度相同
- A走A+B的路程，B走B+A的路程，总路程相同
- 所以会在交点处相遇
如果不相交呢？两个指针都会走到null，循环结束，返回null。
这个方法太巧妙了！代码也非常简洁。
第五步：验证边界情况
- A为空，B为空：返回null ✓
- A为空，B不为空：返回null ✓
- A和B完全相同：返回headA ✓
- A和B不相交：返回null ✓
解法一：双指针切换链表
当前代码里的 getIntersectionNode 是最优写法：
let A = headA;
let B = headB;
while (A != B) {
A = A != null ? A.next : headB;
B = B != null ? B.next : headA;
}
return A;代码逐行解释
let A = headA;定义指针 A，初始指向链表 A 的头节点。
let B = headB;定义指针 B，初始指向链表 B 的头节点。
while (A != B) {循环条件：当两个指针指向不同节点时，继续前进。当它们指向同一个节点（相交点）或都指向 null（不相交）时，循环结束。
A = A != null ? A.next : headB;如果指针 A 还没走到链表 A 的末尾，就继续向后走；如果已经走到末尾（null），就切换到链表 B 的头节点开始走。
B = B != null ? B.next : headA;同理，如果指针 B 还没走到链表 B 的末尾，就继续向后走；如果已经走到末尾，就切换到链表 A 的头节点开始走。
}
return A;循环结束时，A 和 B 要么都指向相交节点，要么都指向 null，返回 A 即可。
算法思想
两个链表的长度可能不同，所以直接一起走时，两个指针不一定能在相交节点处同时到达。
解决办法是让两个指针都走完相同的总路程：
- 指针
A先走链表 A，走到结尾后切到链表 B。 - 指针
B先走链表 B，走到结尾后切到链表 A。
这样两个指针最终都会走过：
A 链表长度 + B 链表长度如果两个链表相交，那么两个指针会在第一个公共节点相遇。
如果两个链表不相交，那么两个指针最终都会走到 null，此时 A == B，循环结束并返回 null。
为什么这样能对齐
假设：
- 链表 A 独有部分长度是
a - 链表 B 独有部分长度是
b - 公共部分长度是
c
那么：
- 指针
A走的路径是：a + c + b - 指针
B走的路径是：b + c + a
在进入公共部分之前，它们走过的总长度都会被补齐，因此会在公共部分的入口节点相遇。
本质上，这个方法不是提前计算长度差，而是通过“切换链表”自动消除长度差。
解法二：计算长度并对齐
当前代码里的 getIntersectionNode2 使用的是更直观的长度对齐法。
步骤：
- 分别遍历两个链表，得到长度
a_length和b_length。 - 让较长链表的指针先走
abs(a_length - b_length)步。 - 然后两个指针一起向后走。
- 第一次指针相等的位置，就是相交节点。
- 如果一直走到
null都不相等，说明不相交。
两种写法的关系
长度对齐法是显式对齐：
先算长度差，再让长链表先走双指针切换法是隐式对齐：
不算长度差，通过走 A+B 和 B+A 自动对齐两者的核心思想都是一样的：让两个指针在距离尾部相同的位置开始同步前进。
复杂度
- 时间复杂度：
O(m + n) - 空间复杂度：
O(1)
其中 m 和 n 分别是两个链表的长度。