面试52题：
题目：两个链表的第一个公共节点
题：输入两个链表，找出它们的第一个公共节点。
解题思路：
①蛮力法：在第一个链表上顺序遍历每个节点，每遍历到一个节点，就在第二个链表上顺序遍历每个节点，直到找到第二个链表上有节点和第一个链表上的节点一样停止。（O(mn)）
②如果从两个链表的尾部开始往前比较（后进先出），那么最后一个相同节点就是我们要找的节点，为此可以借助两个栈，栈顶元素都一样则pop出去，知道找到最后一个相同的元素为止。（时间复杂度O(m+n),且需要额外辅助空间）
③首先遍历两个链表得到它们的长度，如果m>n，则m链表先走m-n步，然后两个链表再同时走，直到找到第一个相同的节点（即为它们的第一个公共节点）。（推荐，时间复杂度O(m+n),且不需要额外辅助空间）
解题代码：
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
length1=self.GetLength(pHead1)
length2=self.GetLength(pHead2) if length1>length2:
headLong=pHead1
headShort=pHead2
else:
headLong=pHead2
headShort=pHead1
diff=abs(length1-length2) for i in range(diff):
headLong=headLong.next while headLong!=None and headShort!=None and headLong!=headShort:
headLong=headLong.next
headShort=headShort.next
return headLong def GetLength(self,pHead):
length=0
while pHead:
pHead=pHead.next
length += 1
return length
