1. 常规思路
既然题目已经明知是两个无环的单链表，那么此题难度就降低了。常规思路就是用一个哈希集合来存储第一个链表遍历后的所有节点；接着遍历第二个链表，与哈希集合中的节点进行比较：
- 如果第二个链表中节点不存在于哈希集合中，那么移动到下一个节点再比较；
- 否则，节点存在于哈希集合中，返回第二个链表的该节点（他就是我们要找的第一个公共节点）。
PS：如果比较到最后一个节点发现，第二个链表中的节点都不存在于哈希集合中，那么说明这两个链表不相交！直接返回None即可。
2. 图解示例
根据示例一，可以得到如下的黄色链表A和蓝色链表B：
然后进行遍历比较操作：
同样不相交的链表示例二如下：
2. 核心代码
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
#
# @param pHead1 ListNode类
# @param pHead2 ListNode类
# @return ListNode类
#第一种解法：哈希
class Solution:
def FindFirstCommonNode(self , pHead1 , pHead2 ):
# write code here
#首先判断两个链表是否为空
if pHead1 is None or pHead2 is None:
return None
#定义链表1 的集合
set_A = set()
node1, node2 = pHead1, pHead2 #定义两个节点
#遍历链表 1 ，把每个节点加入集合中
while node1:
set_A.add(node1)
node1 = node1.next
#遍历链表2 看当前节点是否在 集合中；如果存在，当前节点就是要找的第一个公共节点；否则继续比较下一个节点。
#这里还要注意，如果遍历完链表 B，发现所有节点都不在集合中，则说明两个链表不相交，返回None。
while node2:
if node2 in set_A:
return node2
node2 = node2.next
return None3. 复杂度分析
- 时间复杂度：
(需要遍历链表1，这里m代表链表1 的长度；同理n 就是遍历链表2的时间） - 空间复杂度：
(因为创建的哈希集合要存储链表1的所有节点，所以为m)
--------------------------------------------我是解法二的分割线--------------------------------------------------
4. 解法二：双指针思路
4.1 思路+图解
看到这里有两个链表，那么双指针又可以出来秀一把了。具体步骤如下：
- 创建两个指针A和B分别指向两链表的初始节点，然后让指针A遍历链表1的所有节点；同理指针B也遍历链表2的所有节点；
- 当指针A和指针B都遍历完各自的节点后，开始互换赛道，让指针A去走链表2；而指针B则走链表1；
- 依然是遍历，但是这次两指针就会在某一个点相遇！这个相遇点就是我们要找的第一个公共节点。
PPS：也许有朋友要疑问：如果他们没有相交点呢？放心，因为不相交，所以他们最后都会走到一个None的节点，此时返回该节点即可。
下面是图解示例一，当两链表相交的时候👇：
持续这个过程，直到指针A和指针B走完各自的节点：
现在指针A换到链表2的赛道上，指针B换到链表1的赛道，只要节点不相等继续往下一个节点移动：
最后他们就会在node 6 这里相遇：
同样示例二的不相交过程如下：
4.2 核心代码
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
# @param pHead1 ListNode类
# @param pHead2 ListNode类
# @return ListNode类
#第二种解法：双指针
class Solution:
def FindFirstCommonNode(self , pHead1 , pHead2 ):
# write code here
#首先判断两个链表是否为空
if pHead1 is None or pHead2 is None:
return None
#使用双指针思路进行判断
p1, p2 = pHead1, pHead2 #创建两个指针，分别指向两个链表的头节点
#当指针指向的两个节点不相等：
while p1 != p2:
if p1:
p1 = p1.next #同时更新两个指针
else:
p1 = pHead2
#直到p1走完了自己的节点，p2也走完了自己的节点，此时p1换到p2的这条道上；同理p2也走到p1的道上
#两者还是每次都移动到下一个节点，最终p1会跟p2在某一个节点相遇，相遇的这个节点就是他们的公共节点！
if p2:
p2 = p2.next
else:
p2 = pHead1
return p1 #由于没有交点的时候，两个链表最后都会出现都是None值，所以此时返回的p1 = None 4.3 复杂度分析：
- 时间复杂度：
(其中m 和n 是分别是链表1和链表2的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次) - 空间复杂度：
(两指针使用常数大小的额外空间)
京公网安备 11010502036488号