剑指offer:两个链表的第一个公共结点
题目描述
输入两个链表,找出它们的第一个公共结点。
# -*- 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
声明:本站所有文章资源内容,如无特殊说明或标注,均为采集网络资源。如若本站内容侵犯了原著者的合法权益,可联系本站删除。