1. 问题描述与解法概述LeetCode 160题相交链表是一个经典的链表操作问题。题目给定两个单链表的头节点headA和headB要求找出并返回两个链表相交的起始节点。如果两个链表没有相交则返回null。这个问题的关键在于理解相交的定义两个链表在某个节点开始合并后续节点完全重合。需要注意的是这里的相交是基于节点引用内存地址的比较而非节点值的比较。1.1 解法思路分析对于这个问题主要有两种经典解法哈希集合法利用哈希集合存储节点引用通过空间换时间的方式解决问题双指针法通过巧妙的指针遍历方式在不使用额外空间的情况下解决问题这两种方法各有优劣哈希集合法思路直观但需要额外空间双指针法空间效率高但理解起来有一定难度。下面我们将分别详细解析这两种解法。2. 哈希集合解法详解2.1 基本思路哈希集合法的核心思想很简单遍历其中一个链表将所有节点引用存入哈希集合然后遍历另一个链表检查每个节点是否存在于集合中。第一个存在于集合中的节点就是相交节点。这种方法的时间复杂度是O(mn)空间复杂度是O(m)或O(n)其中m和n分别是两个链表的长度。2.2 代码实现与解析public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // 使用哈希集合存储节点引用 SetListNode 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(mn)但空间复杂度降到了O(1)。3.2 数学原理为什么这种方法有效让我们从数学角度分析设链表A独有部分长度为a链表B独有部分长度为b公共部分长度为c那么pA走过的路径为a c bpB走过的路径为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(mn)O(m)或O(n)双指针法O(mn)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 算法思维培养解决这个问题需要培养以下算法思维空间换时间哈希集合法的核心思想双指针技巧链表问题的常用技巧数学归纳分析指针移动的数学规律边界思考全面考虑各种特殊情况在实际编程中我经常发现初学者容易陷入必须一次性想出最优解的误区。其实算法能力的提升是一个渐进的过程。以这个问题为例先想出哈希集合解法再逐步优化到双指针解法是完全合理的思考路径。重要的是理解每种解法背后的原理和适用场景而不是死记硬背解法代码。