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

本文涉及的产品
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
简介: 深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)

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

期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️

在本篇文章中,我们将详细解读力扣第160题“相交链表”。通过学习本篇文章,读者将掌握如何使用多种方法来解决这一问题,并了解相关的复杂度分析。每种方法都将配以详细的解释和ASCII图解,以便于理解。

问题描述

力扣第160题“相交链表”描述如下:

给你两个单链表的头节点 headAheadB,请你找出并返回它们的相交节点。如果两个链表没有交点,返回 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. 步骤
  • 初始化两个指针 pApB,分别指向链表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 处相交。
  1. 测试案例 2
  • 输入: listA = [1,9,1,2,4], listB = [3,2,4]
  • 输出: 相交节点的值为 2
  • 解释: 两个链表在节点 2 处相交。
  1. 测试案例 3
  • 输入: listA = [2,6,4], listB = [1,5]
  • 输出: 两个链表不相交。
  • 解释: 两个链表没有相交节点。

总结

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

参考资料

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

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

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

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

相关文章
|
3天前
【数据结构OJ题】相交链表
力扣题目——相交链表
13 1
【数据结构OJ题】相交链表
|
21天前
|
Java
力扣经典150题第五十八题:合并两个有序链表
力扣经典150题第五十八题:合并两个有序链表
16 2
|
21天前
|
Java
力扣经典150题第六十题:反转链表 II
力扣经典150题第六十题:反转链表 II
11 1
|
21天前
|
存储 Java
力扣经典150题第五十九题: 随机链表的复制
力扣经典150题第五十九题: 随机链表的复制
13 1
|
24天前
|
索引
力扣每日一题 6/17 枚举+双指针
力扣每日一题 6/17 枚举+双指针
11 1
|
1月前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
19 2
|
1月前
|
Java Python
二刷力扣--链表
二刷力扣--链表
|
1月前
|
存储 算法 数据可视化
【模拟面试问答】深入解析力扣163题:缺失的区间(线性扫描与双指针法详解)
【模拟面试问答】深入解析力扣163题:缺失的区间(线性扫描与双指针法详解)
|
1月前
|
算法 数据挖掘 Java
深入解析力扣167题:两数之和 II(双指针法详解及模拟面试问答)
深入解析力扣167题:两数之和 II(双指针法详解及模拟面试问答)
|
1月前
|
存储 算法 数据挖掘
【模拟面试问答】力扣165题:比较版本号(逐个比较与双指针法详解及模拟面试问答)
【模拟面试问答】力扣165题:比较版本号(逐个比较与双指针法详解及模拟面试问答)

推荐镜像

更多