面试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 = Noneclass 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
转载于:https://www.cnblogs.com/yanmk/p/9231287.html