LCR 023. 相交链表

一.题目：

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(m+n)，就是两个链表都要遍历一次，第一次生成哈希表，第二次查找哈希表，相当于用哈希表比对两个链表。有了这种解法，

自然会想到直接比较两个链表，不用哈希表做中间过渡，就是双指针法，先实现哈希表法如下：

【双指针法】

这个算法理解起来复杂的地方在于，一个链表会遍历多次，很难分析清楚，即使给出了答案还是不相信哈哈。可以看看上面的B站视频自己画图分析下：

A,B指针开始同步走，A链条长，B链条短，假设A相交前长度x,每个节点标号1-6，B相交前长度y，相交前节点标号7。因为B链条短，所以B走了y+z后到

终点了，此时A还在x上走，此时它俩走过的路径长度相同，因为同步走。此时B跳到链表A起点并且比A落后了A走过的节点，假设是u，然后A到达终点的时候

，B走过了x+z-u个节点，此时A跳到链表B起点，当A到达交叉点时A走过了x+z+y个节点，B走过了y+z+x个节点，两者相等又是同步走的，所以二者会相遇。

编程技巧：

1.python的哈希表是用字典代替的，这道题的哈希表解法也考察了python字典的初始化、赋值、查询，分别如下：

类似列表的创建方法：s={}

赋值：s[key]=value

查询：s.get(key)

2.遍历链表直接用while p: p=p.next即可，如果直接用头指针遍历，就用头指针替代p即可，如果链表节点数>=0，while循环执行次数>=0