深入解析力扣160题：相交链表的解决方法（哈希表法与双指针法详细图解）

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！

• 推荐：数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
  
• 导航：

• 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]
输出: 两个链表不相交。

解题思路

1. 初步分析：

• 给定两个链表，要求找出它们的相交节点。
• 可以使用哈希表存储链表A的所有节点，然后遍历链表B，找出第一个出现在哈希表中的节点。
• 也可以使用双指针法，以达到更高的效率。

方法一：哈希表

1. 步骤：

• 初始化一个哈希表 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

方法二：双指针法

1. 步骤：

• 初始化两个指针 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. 测试案例 1：

• 输入: listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]
• 输出: 相交节点的值为 8
• 解释: 两个链表在节点 8 处相交。

2. 测试案例 2：

• 输入: listA = [1,9,1,2,4], listB = [3,2,4]
• 输出: 相交节点的值为 2
• 解释: 两个链表在节点 2 处相交。

3. 测试案例 3：

• 输入: listA = [2,6,4], listB = [1,5]
• 输出: 两个链表不相交。
• 解释: 两个链表没有相交节点。

总结

本文详细解读了力扣第160题“相交链表”，通过哈希表法和双指针法两种方法，高效地解决了这一问题。希望读者通过本文的学习，能够在力扣刷题的过程中更加得心应手。

参考资料

• 《算法导论》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
• 力扣官方题解

🌹🌹如果觉得这篇文对你有帮助的话，记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励，非常感谢 ❥(^_-)

❤️❤️关注公众号 数据分析螺丝钉 回复 学习资料 领取高价值免费学习资料❥(^_-)

欢迎关注微信公众号 数据分析螺丝钉