剑指offer--面试题37：两个链表的第一个公共结点



题目描述

输入两个链表，找出它们的第一个公共结点。 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         if pHead1 is None or pHead2 is None:             return None         len1, len2 = self.getLen(pHead1), self.getLen(pHead2)         #让head1指向更短的链表         if len1>len2:             pHead1, pHead2 = pHead2, pHead1             len1, len2 = len2, len1                       gap = len2-len1         p1 = pHead1         p2 = pHead2         while gap:             p2 = p2.next             gap -= 1                   while p1:             if p1!=p2:                 p1=p1.next                 p2=p2.next             else:                 return p1         return None                             def getLen(self, head):         if head is None:             return 0         p = head         cnt = 0         while p:             cnt += 1             p = p.next         return cnt