剑指Offer52.两个链表的第一个公共节点 哈希表与双指针思路

简介: 剑指Offer52.两个链表的第一个公共节点 哈希表与双指针思路

剑指Offer52.两个链表的第一个公共节点


https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/solution/jian-zhi-offer52liang-ge-lian-biao-de-di-yj5l/

难度:中等


题目

网络异常,图片无法展示
|


注意:


分析

这道题比较容易想到的是,创建一个hash表,然后循环依次A,将A的所有节点添加至Hash表中。

再循环依次B,每次判断B的当前节点是否在hash表中。

代码如下:

class Solution:
    def getIntersectionNode(self, headA, headB):
        d = {}
        while headA:
            d[headA] = headA
            headA = headA.next
        while headB:
            if d.get(headB):
                return headB
            headB = headB.next
        return None

网络异常,图片无法展示
|

这样的思路可以通过,但是题目说了程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

hash表构造了额外的O(n)空间复杂度,那么如何来实现使用O(1)的时间复杂度完成呢?来看看下面的图:

网络异常,图片无法展示
|

如果两个链表相交,那么:

X + 1 + Z + Y 必然等于 Y + 1 + Z + X

所以我们可以使用上图的方式,通过双指针的解法,来完成这道题目。具体代码如下:

网络异常,图片无法展示
|

class Solution:
    def getIntersectionNode(self, headA, headB):
        x, y = headA, headB
        while x != y:
            x = x.next if x else headB
            y = y.next if y else headA
        return x



相关文章
|
6天前
|
算法
《剑指offer》之从“尾到头打印链表”题解
《剑指offer》之从“尾到头打印链表”题解
7 2
|
7天前
|
Java
LeetCode题解- 两两交换链表中的节点-Java
两两交换链表中的节点-Java
7 0
|
21天前
|
Java C++ Python
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
23 0
|
29天前
|
Rust 索引
Rust 编程小技巧摘选(6)
Rust 编程小技巧摘选(6)
39 1
Rust 编程小技巧摘选(6)
|
29天前
|
Java Go C++
Golang每日一练(leetDay0114) 矩阵中的最长递增路径、按要求补齐数组
Golang每日一练(leetDay0114) 矩阵中的最长递增路径、按要求补齐数组
23 0
Golang每日一练(leetDay0114) 矩阵中的最长递增路径、按要求补齐数组
|
29天前
|
Java Go C++
Golang每日一练(leetDay0113) 奇偶链表、链表随机节点
Golang每日一练(leetDay0113) 奇偶链表、链表随机节点
27 0
Golang每日一练(leetDay0113) 奇偶链表、链表随机节点
|
1月前
【Leetcode 2487】从链表中移除节点 —— 单调栈
解题思路:维持一个单调递增栈,当栈为空时,记录当前节点为头节点;否则当前节点为栈顶节点的后继节点
LeetCode | 234. 回文链表
LeetCode | 234. 回文链表
LeetCode | 19. 删除链表的倒数第 N 个结点
LeetCode | 19. 删除链表的倒数第 N 个结点
LeetCode | 138. 随机链表的复制
LeetCode | 138. 随机链表的复制