面试题52：链表中的公共节点

题目：
输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

思路：
这道题目需要认真理解题目，公共的链表节点要考虑到长度不一致的问题，共同的节点一定是从某一个节点开始直到结尾，因此需要尾部对齐，然后开始寻找。故本题的思路应该是先将长度较长的链表向后移动，直至与较短长度的链表尾部对齐，然后同时开始向后，寻找第一个相同的节点即可。

52 两个链表的第一个公共节点.png

代码实现：

# -*- 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
        #1.得到链表的长度
        len1 = self.lenLink(pHead1)
        len2 = self.lenLink(pHead2)
        if len1 > len2:
            dif = len1-len2
            Long = pHead1
            short = pHead2
        else:
            dif = len2-len1
            Long = pHead2
            short = pHead1

        #2.长链表先行
        for i in range(dif):
            Long = Long.next
        
        #3.循环寻找
        while Long != None and short != None and Long != short:
            Long = Long.next
            short = short.next
        return Long



    def lenLink(self,pHead):
        if pHead == None:
            return 0
        count = 0
        while pHead != None:
            count+=1
            pHead = pHead.next
        return count

提交结果：