尧图网站建设 免费方案咨询
ARTICLE DETAIL

资讯详情

深耕网站建设、视觉设计与SEO优化的一线实战洞察。

首页/资讯中心/资讯详情

LeetCode 160题：相交链表的哈希集合法与双指针法解析

发布时间：2026/11/5 10:25:02 尧图网站建设
LeetCode 160题：相交链表的哈希集合法与双指针法解析

1. 问题描述与解法概述

LeetCode 160题"相交链表"是一个经典的链表操作问题。题目给定两个单链表的头节点headA和headB，要求找出并返回两个链表相交的起始节点。如果两个链表没有相交，则返回null。

这个问题的关键在于理解"相交"的定义：两个链表在某个节点开始合并，后续节点完全重合。需要注意的是，这里的相交是基于节点引用（内存地址）的比较，而非节点值的比较。

1.1 解法思路分析

对于这个问题，主要有两种经典解法：

  1. 哈希集合法：利用哈希集合存储节点引用，通过空间换时间的方式解决问题
  2. 双指针法：通过巧妙的指针遍历方式，在不使用额外空间的情况下解决问题

这两种方法各有优劣：哈希集合法思路直观但需要额外空间；双指针法空间效率高但理解起来有一定难度。下面我们将分别详细解析这两种解法。

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 注意事项与优化

  1. 节点比较：这里比较的是节点对象引用（内存地址），而非节点值。即使两个节点值相同，如果不是同一个对象，也不算相交。

  2. 空间优化：可以选择将较短的链表存入哈希集合，这样可以减少内存使用。但时间复杂度不变。

  3. 边界条件：

    • 两个链表都为空时直接返回null
    • 一个链表为空，另一个不为空时也直接返回null

提示：在实际面试中，如果先提出哈希集合解法，面试官可能会追问"能否在不使用额外空间的情况下解决这个问题"，这就引出了下面的双指针解法。

3. 双指针解法深入解析

3.1 基本思路

双指针法是一种更巧妙的解法，它不需要额外的存储空间。基本思路是：

  1. 初始化两个指针pA和pB，分别指向headA和headB
  2. 同时移动两个指针，每次各走一步
  3. 当pA到达链表末尾时，让它指向headB；当pB到达链表末尾时，让它指向headA
  4. 如果两指针相遇，则相遇点就是相交节点；如果都走到末尾(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 边界情况处理

  1. 不相交情况：两指针最终会同时为null，循环终止，返回null
  2. 一个链表为空：直接返回null
  3. 相同链表：直接返回头节点
  4. 链表有环：题目假设链表无环，如有环需要先判断环的存在

注意：这种解法依赖于"无环"的假设。如果链表可能有环，需要先使用快慢指针判断是否有环。

4. 两种解法的比较与选择

4.1 时间复杂度对比

解法时间复杂度空间复杂度
哈希集合法O(m+n)O(m)或O(n)
双指针法O(m+n)O(1)

4.2 适用场景

  1. 哈希集合法适用场景：

    • 需要快速实现解决方案
    • 内存空间充足
    • 需要记录访问过的节点用于其他用途

  2. 双指针法适用场景：

    • 内存空间受限
    • 需要最优空间复杂度
    • 作为后续优化的基础

4.3 选择建议

在实际编程中：

  • 如果是面试，建议先提出哈希集合法，再优化到双指针法
  • 如果是实际工程，根据内存限制选择合适的方法
  • 如果是竞赛，通常选择空间最优的双指针法

5. 常见问题与调试技巧

5.1 常见错误

  1. 比较节点值而非引用：

    // 错误写法：比较节点值 if (temp.val == another.val) { ... } // 正确写法：比较节点引用 if (temp == another) { ... }

  2. 忽略指针重置条件：

    // 错误写法：缺少指针重置 while (pA != null && pB != null) { ... }

  3. 循环条件错误：

    // 错误写法：可能导致无限循环 while (true) { ... }

5.2 调试技巧

  1. 可视化调试：画出链表结构图，标注指针位置
  2. 打印日志：在关键步骤打印指针信息
    System.out.println("pA: " + pA + ", pB: " + pB);
  3. 单元测试：编写测试用例覆盖各种情况：
    • 不相交链表
    • 相交链表
    • 一个链表为空
    • 相同链表
    • 链表在头节点相交
    • 链表在尾节点相交

5.3 性能优化

  1. 提前终止：在哈希集合法中，如果其中一个链表遍历完仍未找到交点，可提前终止
  2. 长度比较：可以先计算两链表长度，让长链表的指针先走差值步
  3. 并行遍历：在多线程环境下，可以并行遍历链表提高速度

6. 扩展思考与实际应用

6.1 变种问题

  1. 判断链表是否有环：使用快慢指针
  2. 找到环的起点：结合哈希集合和快慢指针
  3. 合并两个有序链表：类似双指针思想
  4. 链表倒数第k个节点：快慢指针的另一种应用

6.2 实际应用场景

  1. 内存管理：检测内存块是否重叠
  2. 路径查找：判断两条路径是否交汇
  3. 依赖分析：检测软件模块间的依赖关系
  4. 社交网络：寻找两个人之间的共同联系

6.3 算法思维培养

解决这个问题需要培养以下算法思维：

  1. 空间换时间：哈希集合法的核心思想
  2. 双指针技巧：链表问题的常用技巧
  3. 数学归纳：分析指针移动的数学规律
  4. 边界思考：全面考虑各种特殊情况

在实际编程中，我经常发现初学者容易陷入"必须一次性想出最优解"的误区。其实算法能力的提升是一个渐进的过程。以这个问题为例，先想出哈希集合解法，再逐步优化到双指针解法，是完全合理的思考路径。重要的是理解每种解法背后的原理和适用场景，而不是死记硬背解法代码。

网站建设 视觉设计 SEO优化
返回列表