移动网站和定制网站,赣州市建设局,做网站注册验证码,天宁网站建设一.题目#xff1a;
LCR 023. 相交链表 - 力扣#xff08;LeetCode#xff09; 二.我的原始解法-无#xff1a; 三.其他人的正确及好的解法#xff0c;力扣解法参考#xff1a;
哈希表法及双指针法#xff1a;LCR 023. 相交链表 - 力扣#xff08;LeetCode#xff0…一.题目
LCR 023. 相交链表 - 力扣LeetCode 二.我的原始解法-无 三.其他人的正确及好的解法力扣解法参考
哈希表法及双指针法LCR 023. 相交链表 - 力扣LeetCode
B站动态讲解双指针处理相交链表过程算法动画题解leetcode.160.相交链表双指针_哔哩哔哩_bilibili 四.对于别人解法的消化及总结
首先要稍微回顾下python实现链表的方法题目中已经给出如下链表类型定义初始化函数中有数值部分和指针部分然后又给出了要实现
算法的函数入参两个链表的头结点headA和headB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next None
def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode: 【哈希表法】就是判断两个链表的指针地址相同说明两个链表指向了同一个节点这样就找到了交叉节点但是要注意实现方法和列表查询的不同
列表查询用index简单遍历或者内置函数操作即可链表查询要注意指针问题。判断两个链表的指针相同可以用哈希表法就是把一个链表的已
遍历节点放到一个哈希表中然后使用哈希表查找时间复杂度为O(1)的特点直接用另一个链表的每个节点在哈希表中匹配匹配一致的返回即可
这种方法的时间复杂度为O(mn)就是两个链表都要遍历一次第一次生成哈希表第二次查找哈希表相当于用哈希表比对两个链表。有了这种解法
自然会想到直接比较两个链表不用哈希表做中间过渡就是双指针法先实现哈希表法如下 【双指针法】
这个算法理解起来复杂的地方在于一个链表会遍历多次很难分析清楚即使给出了答案还是不相信哈哈。可以看看上面的B站视频自己画图分析下 A,B指针开始同步走A链条长B链条短假设A相交前长度x,每个节点标号1-6B相交前长度y相交前节点标号7。因为B链条短所以B走了yz后到
终点了此时A还在x上走此时它俩走过的路径长度相同因为同步走。此时B跳到链表A起点并且比A落后了A走过的节点假设是u然后A到达终点的时候
B走过了xz-u个节点此时A跳到链表B起点当A到达交叉点时A走过了xzy个节点B走过了yzx个节点两者相等又是同步走的所以二者会相遇。 编程技巧
1.python的哈希表是用字典代替的这道题的哈希表解法也考察了python字典的初始化、赋值、查询分别如下
类似列表的创建方法s{}
赋值s[key]value
查询s.get(key)
2.遍历链表直接用while p: pp.next即可如果直接用头指针遍历就用头指针替代p即可如果链表节点数0while循环执行次数0
