刷题记录：两个链表的第一个公共结点

本来想魔怔快慢指针的，发现好像不太行
于是先魔怔哈希表
代码如下：

def FindFirstCommonNode(self , pHead1 , pHead2 ):
    hashtable = dict()
    i = 0
    while pHead1:                  # 将 pHead1 中的结点存入哈希表
        hashtable[pHead1] = i
        pHead1 = pHead1.next
        i += 1

    while pHead2:                  # 在 pHead2 中寻找第一个相同的结点
        if pHead2 in hashtable:
            return pHead2
        pHead2 = pHead2.next
    
    return None

然后想了想，好像可以上双指针
具体思想是先获取两列表的长度，得到长度之差 k
令长的列表头指针先行移动 k 步，再同时移动
代码如下：

def FindFirstCommonNode(self , pHead1 , pHead2 ):
    i1 = self.GetLength(pHead1)     # 获取长度
    i2 = self.GetLength(pHead2)

    k = 0
    p1, p2 = pHead1, pHead2         # 获得差值 k
    if i1 < i2:                     # 同时使最长的链表为 p1
        k = i2 - i1
        p1, p2 = pHead2, pHead1
    else:
        k = i1 - i2
    
    for _ in range(k):              # 使 p1 先走 k 步
        p1 = p1.next
    
    while p1 != p2 and p1 and p2:   # 同时移动 p1 和 p2
        p1 = p1.next                # 寻找相同的结点
        p2 = p2.next                # 没有则 p1 == p2 == None

    return p1


def GetLength(self, head):          # 获得链表长度
    i = 0
    while head:
        head = head.next
        i += 1
    
    return i

但我觉得这样还不够，于是查看评论区
发现自己的思路正确，但做法还不够简洁，于是便有如下想法：

令 p1, p2 同时移动，先抵达表尾的指针代表该链表最短，此时 p1, p2之间的距离刚好为差值 k
若 p1 先抵达表尾，则 pHead1 为短链表，p2 为长链表。令 p1 指向 pHead2 ，再与 p2 同时移动。当 p2 抵达表尾时，此时 p1 已经移动 k 步，令 p2 指向 pHead1 ，当 p1 = p2 时找到公共结点。（若 p2 先抵达队尾同理） 若 p1, p2 同长，则相等时找到公共结点，为 None 时为没有公共结点

代码如下：

def FindFirstCommonNode(self , pHead1 , pHead2 ):
    p1, p2 = pHead1, pHead2
    while p1 != p2:
        p1 = p1.next if p1 else pHead2
        p2 = p2.next if p2 else pHead1

    return p1

妙啊