您的当前位置:首页正文

算法-链表-BM10 两个链表的第一个公共结点

2024-11-20 来源:个人技术集锦


输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空。(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的)。下图来自牛客:

  • 这里使用快慢法则,将两条链表串在一起。即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
显示全文