两个链表的第一个公共结点（python实现）

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    """
    # 方法一，利用两个栈
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        stack1 = []
        stack2 = []
        # pHead1进栈
        if pHead1==None or pHead2==None:
            return None
        while pHead1:
            stack1.append(pHead1)
            pHead1 = pHead1.next
        # pHead2进栈
        while pHead2:
            stack2.append(pHead2)
            pHead2 = pHead2.next
        node = None
        while stack1 and stack2 and stack1[-1] is stack2[-1]:
            node = stack1.pop()
            stack2.pop()
        return node
    """
    """
    # 方法2:利用两个链表的长度差
    def FindFirstCommonNode(self, pHead1, pHead2):
        if pHead1==None or pHead2==None:
            return None
        len1 = self.GetListLength(pHead1)
        len2 = self.GetListLength(pHead2)
        if len1>= len2:
            len_diff = len1-len2
            while len_diff > 0:
                pHead1 = pHead1.next   # 长的链表先走完这个长度差
                len_diff -= 1
        else:
            len_diff = len2 - len1
            while len_diff > 0:
                pHead2 = pHead2.next
                len_diff -= 1
        while pHead1 != pHead2:
            pHead1 = pHead1.next
            pHead2 = pHead2.next
        return pHead1

    def GetListLength(self,pHead):
        length = 0
        pNode = pHead
        while pNode != None:
            length += 1
            pNode = pNode.next
        return length
    """
    # 方法三：循环,将一个链表中的所有值存入进去，然后借助另一个链表去找到公共节点
    def FindFirstCommonNode(self, pHead1, pHead2):
        if pHead1 == None or pHead2 == None:
            return None
        list1 = []
        while pHead1:
            list1.append(pHead1.val)
            pHead1 = pHead1.next
        while pHead2:
            if pHead2.val in list1:
                return pHead2
            else:
                pHead2 = pHead2.next