输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空。(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的)。下图来自牛客:
curA
走完pHead1
链表就去走pHead2
链表,curB
也是一样。如果两链表存在交点,则必然在交点相遇。例如,A
链表为1+1
,B
链表为2+1
,那么curA
在走完A
的2个节点后,进入B
再走两个节点;与curB
在走完B
的3个节点后,进入A
再走一个节点;相遇在交点处。都走了4步。None
“相遇”。class Solution:
def FindFirstCommonNode(self , pHead1 , pHead2 ):
# write code here
curA=pHead1
curB=pHead2
while curA!=curB:
curA=curA.next if curA else pHead2
curB=curB.next if curB else pHead1
return curA