题解 | 两个链表的第一个公共结点-双指针-哈希

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param pHead1 ListNode类 
# @param pHead2 ListNode类 
# @return ListNode类
#
class Solution:
    def FindFirstCommonNode1(self , pHead1 , pHead2 ):
        # write code here
        # 解法1 ：  哈希表存储  空间复杂度O(n)    不符合和题目要求
        arr=set()
        cur =pHead1
        while cur:
            arr.add(cur)
            cur=cur.next
        cur2=pHead2
        while cur2:
            if cur2 in arr:
                return cur2
            cur2=cur2.next
        return None
    """
     解法2 ： 
     1. 分别得到两个链表长度m,n 。
     2. 求m,n 的长度差值 k ,较长的链表先走k 步。
     3. 然后两个指针分别指向两个链表头结点，同时遍历，遇到第一个相同的节点就是第一个公共节点。
     题目中案例 
     m=5  n =4  k=1 
     第一个链表先走k=1 ,然后两个链表同时
    """
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        #判空处理
        if not pHead1 or not pHead2:
            return None
        cur1=pHead1
        cur2=pHead2
        m =0
        n=0 
        while cur1:
            m+=1
            cur1=cur1.next
        while cur2:
            n+=1
            cur2=cur2.next
        cur1=pHead1
        cur2=pHead2    
        if m>n:
            k=m-n 
            for i in   range(k):
                cur1=cur1.next
        else:
            k=n-m
            for i in range(k):
                cur2=cur2.next
        while cur1 and cur2:
            if cur1==cur2:
                return cur1
            cur1=cur1.next
            cur2=cur2.next
        return None