[牛客网刷题 Day2] JZ52 两个链表的第一个公共结点（没做出来）双指针巧解

本文主要是介绍[牛客网刷题 Day2] JZ52 两个链表的第一个公共结点（没做出来）双指针巧解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

思考过程：

好像想的太复杂了，首先固定phead1，寻找val一样的phead2，找到的话，就都往右移动一位；否则phead+1。可是需要注意好多好多的边界啊，写了好久好久，最后还是好几个用例通不过，只能根据用例慢慢改，可是怎么改都不对。o(╥﹏╥)o

class Solution:def FindFirstCommonNode(self , pHead1 , pHead2):# write code hereif pHead1==None or pHead2==None:return Nonedummy2 = pHead2while pHead1.next:while pHead1.val != pHead2.val:pHead2 = pHead2.next# 找完了都找不到相同值，l1+1，l2返回初始位置if pHead2 == None:pHead1 = pHead1.nextpHead2 = dummy2if pHead1 == None:return None# 找到相同值，都移动一位,dummy重新赋值else:dummy2 = pHead2if not(pHead1.next and pHead2.next):pHead2 = dummy2continuewhile pHead1.next or pHead2.next:if pHead1.next.val == pHead2.next.val:pHead1 = pHead1.nextpHead2 = pHead2.nextif pHead1.next == None and pHead2.next == None:return dummy2else:pHead1 = pHead1.nextif pHead1 == None:return pHead2.nextbreakelse: return dummy2return None

答案：

常规思路，跟我的思路差不多，但是他用到了哈希表。
啊啊啊，原来链表是可以比较的！可以使用in，可是我的编译器不能这样操作。。。
所以我是能做出这道题的呢！

啊啊啊啊啊啊，发现问题了！！我初始化链表的时候搞错了！应该创建三个链表，前两个再指向第三个呢！

常规思路就是用一个哈希集合来存储第一个链表遍历后的所有节点；接着遍历第二个链表，与哈希集合中的节点进行比较：

如果第二个链表中节点不存在于哈希集合中，那么移动到下一个节点再比较；
否则，节点存在于哈希集合中，返回第二个链表的该节点（他就是我们要找的第一个公共节点）。
PS：如果比较到最后一个节点发现，第二个链表中的节点都不存在于哈希集合中，那么说明这两个链表不相交！直接返回None即可。

# 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 node2node2 = node2.nextreturn None

还有一个复杂的双指针思路，啊！
哇！太巧妙了吧！原理是：走一遍pHead1，再走一遍pHead2的总路程一定是相等的！

# 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.nextelse:p2 = pHead1return p1                  #由于没有交点的时候，两个链表最后都会出现都是None值，所以此时返回的p1 = None          

这篇关于[牛客网刷题 Day2] JZ52 两个链表的第一个公共结点（没做出来）双指针巧解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---