JZ36 两个链表的第一个公共结点 python

my version

class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        if pHead1 is None or pHead2 is None:
            return None

        dic = {}
        len1, len2 = 0, 0
        p = pHead1
        while p:
            if p.val not in dic:
                dic[p.val] = 0
            dic[p.val] += 1
            p = p.next
            len1 += 1
        p = pHead2
        while p:
            if p.val not in dic:
                dic[p.val] = 0
            dic[p.val] += 1
            p = p.next
            len2 += 1
        p = pHead1 if len1 >= len2 else pHead2 
        while p and dic[p.val]<2:
            p = p.next
        return p

可能出现问题 当两个链表中出现相同的值，但并非公共节点，改进直接存节点:

class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        if pHead1 is None or pHead2 is None:
            return None
        nodes = set()
        p = pHead1
        while p:
            nodes.add(p)
            p = p.next
        p = pHead2
        while p:
            if p in nodes:
                return p
            p = p.next
        return None

book version
双指针

class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        if pHead1 is None or pHead2 is None:
            return None
        p1, p2 = pHead1, pHead2
        while p1 is not p2:
            p1 = p1.next if p1 else pHead2
            p2 = p2.next if p2 else pHead1
        return p1