❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！
- 推荐：数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
- 导航：
- LeetCode解锁1000题: 打怪升级之旅：每题都包括3-5种算法，以及详细的代码实现，刷题面试跳槽必备
- 漫画版算法详解：通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读，看一遍就掌握
- python源码解读：解读python的源代码与调用关系，快速提升代码质量
- python数据分析可视化：企业实战案例：企业级数据分析案例与可视化，提升数据分析思维和可视化能力
- 程序员必备的数学知识与应用：全面详细的介绍了工程师都必备的数学知识
期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️
在本篇文章中，我们将详细解读力扣第160题“相交链表”。通过学习本篇文章，读者将掌握如何使用多种方法来解决这一问题，并了解相关的复杂度分析。每种方法都将配以详细的解释和ASCII图解，以便于理解。
问题描述
力扣第160题“相交链表”描述如下：
给你两个单链表的头节点
headA和headB，请你找出并返回它们的相交节点。如果两个链表没有交点，返回null。
题目数据保证整个链式结构中不存在环。
注意，函数返回结果后，链表必须保持其原始结构。
示例 1:
输入: listA = [4,1,8,4,5], listB = [5,6,1,8,4,5] 输出: 相交节点的值为 8 解释: 两个链表在节点 8 处相交。
示例 2:
输入: listA = [1,9,1,2,4], listB = [3,2,4] 输出: 相交节点的值为 2 解释: 两个链表在节点 2 处相交。
示例 3:
输入: listA = [2,6,4], listB = [1,5] 输出: 两个链表不相交。
解题思路
- 初步分析：
- 给定两个链表，要求找出它们的相交节点。
- 可以使用哈希表存储链表A的所有节点，然后遍历链表B，找出第一个出现在哈希表中的节点。
- 也可以使用双指针法，以达到更高的效率。
方法一：哈希表
- 步骤：
- 初始化一个哈希表
nodes。 - 遍历链表A，将每个节点存储在哈希表中。
- 遍历链表B，检查每个节点是否在哈希表中。如果在，则该节点为相交节点。
- 如果遍历完链表B都没有找到相交节点，则返回
null。
代码实现
class ListNode: def __init__(self, x): self.val = x self.next = None def getIntersectionNode(headA, headB): nodes = set() current = headA while current: nodes.add(current) current = current.next current = headB while current: if current in nodes: return current current = current.next return None
ASCII图解
假设链表A和链表B在节点8处相交，图解如下：
链表A: 4 -> 1 -> 8 -> 4 -> 5 链表B: 5 -> 6 -> 1 -> 8 -> 4 -> 5 哈希表存储链表A的节点: {4, 1, 8, 4, 5} 遍历链表B，找到第一个在哈希表中的节点: 5 -> 6 -> 1 (不在) -> 8 (在) 返回相交节点 8
方法二：双指针法
- 步骤：
- 初始化两个指针
pA和pB，分别指向链表A和链表B的头节点。 - 让两个指针同时遍历链表，当一个指针到达链表末尾时，将其指向另一个链表的头节点。
- 当两个指针相遇时，所指向的节点即为相交节点。如果两个指针遍历完所有节点都没有相遇，则返回
null。
代码实现
class ListNode: def __init__(self, x): self.val = x self.next = None def getIntersectionNode(headA, headB): if not headA or not headB: return None pA, pB = headA, headB while pA != pB: pA = pA.next if pA else headB pB = pB.next if pB else headA return pA
ASCII图解
假设链表A和链表B在节点8处相交，图解如下：
链表A: 4 -> 1 -> 8 -> 4 -> 5 链表B: 5 -> 6 -> 1 -> 8 -> 4 -> 5 初始化指针: pA = 4, pB = 5 第一次遍历: pA: 4 -> 1 -> 8 -> 4 -> 5 -> 5 -> 6 -> 1 -> 8 pB: 5 -> 6 -> 1 -> 8 -> 4 -> 5 -> 4 -> 1 -> 8 相遇在节点 8 返回相交节点 8
复杂度分析
- 时间复杂度：
- 哈希表法：O(m + n)，其中 m 和 n 分别是链表A和链表B的长度。
- 双指针法：O(m + n)，其中 m 和 n 分别是链表A和链表B的长度。
- 空间复杂度：
- 哈希表法：O(m)，需要额外的空间来存储链表A的所有节点。
- 双指针法：O(1)，只使用了常数空间。
测试案例分析
- 测试案例 1：
- 输入:
listA = [4,1,8,4,5],listB = [5,6,1,8,4,5] - 输出: 相交节点的值为
8 - 解释: 两个链表在节点
8处相交。
- 测试案例 2：
- 输入:
listA = [1,9,1,2,4],listB = [3,2,4] - 输出: 相交节点的值为
2 - 解释: 两个链表在节点
2处相交。
- 测试案例 3：
- 输入:
listA = [2,6,4],listB = [1,5] - 输出: 两个链表不相交。
- 解释: 两个链表没有相交节点。
总结
本文详细解读了力扣第160题“相交链表”，通过哈希表法和双指针法两种方法，高效地解决了这一问题。希望读者通过本文的学习，能够在力扣刷题的过程中更加得心应手。
参考资料
- 《算法导论》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- 力扣官方题解
🌹🌹如果觉得这篇文对你有帮助的话，记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励，非常感谢 ❥(^_-)
❤️❤️关注公众号 数据分析螺丝钉 回复 学习资料 领取高价值免费学习资料❥(^_-)
欢迎关注微信公众号 数据分析螺丝钉
