1. 问题描述与解法概述
LeetCode 160题"相交链表"是一个经典的链表操作问题。题目给定两个单链表的头节点headA和headB，要求找出并返回两个链表相交的起始节点。如果两个链表没有相交，则返回null。
这个问题的关键在于理解"相交"的定义：两个链表在某个节点开始合并，后续节点完全重合。需要注意的是，这里的相交是基于节点引用（内存地址）的比较，而非节点值的比较。
1.1 解法思路分析
对于这个问题，主要有两种经典解法：
- 哈希集合法：利用哈希集合存储节点引用，通过空间换时间的方式解决问题
- 双指针法：通过巧妙的指针遍历方式，在不使用额外空间的情况下解决问题
这两种方法各有优劣：哈希集合法思路直观但需要额外空间；双指针法空间效率高但理解起来有一定难度。下面我们将分别详细解析这两种解法。
2. 哈希集合解法详解
2.1 基本思路
哈希集合法的核心思想很简单：遍历其中一个链表，将所有节点引用存入哈希集合；然后遍历另一个链表，检查每个节点是否存在于集合中。第一个存在于集合中的节点就是相交节点。
这种方法的时间复杂度是O(m+n)，空间复杂度是O(m)或O(n)，其中m和n分别是两个链表的长度。
2.2 代码实现与解析
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // 使用哈希集合存储节点引用 Set<ListNode> hashTable = new HashSet<>(); ListNode temp = headA; // 遍历链表A，将所有节点加入集合 while (temp != null) { hashTable.add(temp); temp = temp.next; } // 遍历链表B，检查每个节点是否在集合中 temp = headB; while (temp != null) { if (hashTable.contains(temp)) { return temp; // 找到相交节点 } temp = temp.next; } return null; // 没有相交节点 } }2.3 注意事项与优化
节点比较：这里比较的是节点对象引用（内存地址），而非节点值。即使两个节点值相同，如果不是同一个对象，也不算相交。
空间优化：可以选择将较短的链表存入哈希集合，这样可以减少内存使用。但时间复杂度不变。
边界条件：
- 两个链表都为空时直接返回null
- 一个链表为空，另一个不为空时也直接返回null
提示：在实际面试中，如果先提出哈希集合解法，面试官可能会追问"能否在不使用额外空间的情况下解决这个问题"，这就引出了下面的双指针解法。
3. 双指针解法深入解析
3.1 基本思路
双指针法是一种更巧妙的解法，它不需要额外的存储空间。基本思路是：
- 初始化两个指针pA和pB，分别指向headA和headB
- 同时移动两个指针，每次各走一步
- 当pA到达链表末尾时，让它指向headB；当pB到达链表末尾时，让它指向headA
- 如果两指针相遇，则相遇点就是相交节点；如果都走到末尾(null)，则不相交
这种方法的时间复杂度同样是O(m+n)，但空间复杂度降到了O(1)。
3.2 数学原理
为什么这种方法有效？让我们从数学角度分析：
设：
- 链表A独有部分长度为a
- 链表B独有部分长度为b
- 公共部分长度为c
那么：
- pA走过的路径为：a + c + b
- pB走过的路径为：b + c + a
可以看到，两者走过的总长度相同，因此如果有交点，必定会在交点处相遇；如果没有交点，则会同时到达null。
3.3 代码实现
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) return null; ListNode pA = headA, pB = headB; while (pA != pB) { pA = (pA == null) ? headB : pA.next; pB = (pB == null) ? headA : pB.next; } return pA; } }3.4 边界情况处理
- 不相交情况：两指针最终会同时为null，循环终止，返回null
- 一个链表为空：直接返回null
- 相同链表：直接返回头节点
- 链表有环：题目假设链表无环，如有环需要先判断环的存在
注意：这种解法依赖于"无环"的假设。如果链表可能有环，需要先使用快慢指针判断是否有环。
4. 两种解法的比较与选择
4.1 时间复杂度对比
| 解法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 哈希集合法 | O(m+n) | O(m)或O(n) |
| 双指针法 | O(m+n) | O(1) |
4.2 适用场景
哈希集合法适用场景：
- 需要快速实现解决方案
- 内存空间充足
- 需要记录访问过的节点用于其他用途
双指针法适用场景：
- 内存空间受限
- 需要最优空间复杂度
- 作为后续优化的基础
4.3 选择建议
在实际编程中：
- 如果是面试，建议先提出哈希集合法，再优化到双指针法
- 如果是实际工程，根据内存限制选择合适的方法
- 如果是竞赛，通常选择空间最优的双指针法
5. 常见问题与调试技巧
5.1 常见错误
比较节点值而非引用：
// 错误写法：比较节点值 if (temp.val == another.val) { ... } // 正确写法：比较节点引用 if (temp == another) { ... }忽略指针重置条件：
// 错误写法：缺少指针重置 while (pA != null && pB != null) { ... }循环条件错误：
// 错误写法：可能导致无限循环 while (true) { ... }
5.2 调试技巧
- 可视化调试：画出链表结构图，标注指针位置
- 打印日志：在关键步骤打印指针信息
System.out.println("pA: " + pA + ", pB: " + pB); - 单元测试：编写测试用例覆盖各种情况：
- 不相交链表
- 相交链表
- 一个链表为空
- 相同链表
- 链表在头节点相交
- 链表在尾节点相交
5.3 性能优化
- 提前终止：在哈希集合法中，如果其中一个链表遍历完仍未找到交点，可提前终止
- 长度比较：可以先计算两链表长度，让长链表的指针先走差值步
- 并行遍历：在多线程环境下，可以并行遍历链表提高速度
6. 扩展思考与实际应用
6.1 变种问题
- 判断链表是否有环：使用快慢指针
- 找到环的起点：结合哈希集合和快慢指针
- 合并两个有序链表：类似双指针思想
- 链表倒数第k个节点：快慢指针的另一种应用
6.2 实际应用场景
- 内存管理：检测内存块是否重叠
- 路径查找：判断两条路径是否交汇
- 依赖分析：检测软件模块间的依赖关系
- 社交网络：寻找两个人之间的共同联系
6.3 算法思维培养
解决这个问题需要培养以下算法思维：
- 空间换时间：哈希集合法的核心思想
- 双指针技巧：链表问题的常用技巧
- 数学归纳：分析指针移动的数学规律
- 边界思考：全面考虑各种特殊情况
在实际编程中，我经常发现初学者容易陷入"必须一次性想出最优解"的误区。其实算法能力的提升是一个渐进的过程。以这个问题为例，先想出哈希集合解法，再逐步优化到双指针解法，是完全合理的思考路径。重要的是理解每种解法背后的原理和适用场景，而不是死记硬背解法代码。
