题目描述
输入两个链表，找出它们的第一个公共结点。

# -*- coding: utf-8 -*-# @Time : 2019-07-12 22:20# @Author : Jayce Wong# @ProjectName : job# @FileName : findFirstCommonNode.py# @Blog : https://blog.51cto.com/jayce1111# @Github : https://github.com/SysuJayceclass ListNode: def __init__(self, x): self.val = x self.next = Noneclass Solution: """ 两个单向链表的第一个公共节点，如果存在这样的公共节点，那么这两个链表从该节点开始剩余的节点都是 一样的。 解法1： 对于第一个链表，遍历其所有节点，在扫描到第x个节点的时候，从第二个链表中遍历所有节点，如果存在 一个和节点x一样的节点，那么节点x就是第一个公共节点。 这种解法的时间复杂度为O(n^2) 解法2： 前面说到如果两个单向链表存在公共节点，那么从第一个公共节点开始到最后一个节点都是公共节点。 因此，如果我们能从两个链表的末尾节点开始遍历，找到最后一个相同的节点，那么这个节点就是第一个 公共节点。但是这个单向链表不支持反向遍历，因此我们可以利用栈的性质，维护两个辅助栈，分别保存 两个链表的节点，然后每次比较这两个辅助栈的栈顶元素。最后我们就能在O(n)的时间复杂度内解决问题。 解法3： 虽然解法2的时间复杂度已经很优了，但是仍需要用到辅助空间，其实借助快慢指针的思想，我们可以避免 这样的额外空间开销。先计算两个链表的长度，然后先移动长链表的指针，使得长短链表的指针距离各自的 末尾有相同的距离，然后开始同时移动两个指针，直到出现两指针指向的节点相同为止，那么这个相同节点 就是第一个公共节点。 """ def FindFirstCommonNode(self, pHead1, pHead2): # 记录两个链表的长度 len1 = len2 = 0 pNode1 = pHead1 pNode2 = pHead2 while pNode1: pNode1 = pNode1.next len1 += 1 while pNode2: pNode2 = pNode2.next len2 += 1 # 确定哪个链表是长链表，哪个链表是短链表 if len1 > len2: pLong = pHead1 pShort = pHead2 else: pLong = pHead2 pShort = pHead1 # 调整长链表的指针，使得长短链表距离各自末尾节点距离相同 diff = abs(len1 - len2) for i in range(diff): pLong = pLong.next # 同时移动长短链表指针，当出现第一个相同节点(即第一个公共节点)的时候，返回这个节点 while pLong: if pLong == pShort: return pLong pLong = pLong.next pShort = pShort.next # 如果不存在公共节点，返回空指针 return None