两个链表的第一个公共结点

两个链表的第一个公共结点_牛客网

https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=13&tqId=11189&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tPage=2

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

思路:首先我们要知道什么是公共节点,两个链表从某一节点开始,他们的next都指向同一个节点。但由于是单向链表的节点,每个节点只有一个next,因此从第一个公共节点开始,之后他们的所有节点都是重合的,不可能再出现分叉。所以可以先遍历两个链表得到他们的长度,就能知道哪个链表比较长,以及长的链表比短的链表多几个结点。在第二次遍历的时候,在较长的链表上先走若干步,接着同时在两个链表上遍历,找到的第一个相同的结点就是他们的第一个公共结点。时间复杂度为O(m+n),而暴力破解法的时间复杂度为O(mn).

def FindFirstCommonNode(self, pHead1, pHead2):
    # write code here
    p1 = pHead1
    p2 = pHead2
    lenght1 = lenght2 = 0
    while p1:
        lenght1 += 1
        p1 = p1.next
    while p2:
        lenght2 += 1
        p2 = p2.next
    if lenght1 < lenght2:
        pHead1, pHead2 = pHead2, pHead1
    distance = abs(lenght1-lenght2)
    for i in range(distance):
        pHead1 = pHead1.next
    while pHead1 != pHead2:
        pHead1 = pHead1.next
        pHead2 = pHead2.next
    return pHead1
全部评论
如果第一个公共节点在很前面,那么长链先走的时候可能就错过了第一个公共的节点了。
2 回复 分享
发布于 2021-05-21 15:08
在你这里终于明白了公共节点的意思,感觉自己憨憨的,代码终于看懂了
2 回复 分享
发布于 2020-08-30 09:32
思路很清晰也很容易懂,但是这个code 没有通过牛客网的测试用例,不知道为啥
点赞 回复 分享
发布于 2021-04-24 17:29
之前自己脑补了类似于两条直线相交的情形,果然还是基础不够扎实,看了你的解释明白多了。
点赞 回复 分享
发布于 2021-04-18 13:27

相关推荐

01-15 13:45
门头沟学院 Java
牛客92772631...:boss招聘挂岗位是要花钱的,花了钱不挂白不挂,别那么焦虑,但是也要做好跳槽的准备
找实习记录
点赞 评论 收藏
分享
02-07 12:06
已编辑
华侨大学 测试开发
最近看到很多&nbsp;92&nbsp;的,甚至是硕士,开始往测开赛道卷,说实话有点看不懂。先把话说清楚,大厂里的测开,绝大多数时间干的还是测试的活,只是写点自动化脚本、维护测试平台、接接流水线,真正像开发一样做系统、做架构、做核心平台的测开少得可怜,基本都集中在核心提效组,而且人很少,外面进去的大概率轮不到你,我想真正干过人都清楚。很多人被洗脑了,以为测开也是开,和后端差不多,只是更简单、更轻松、还高薪。现实情况是,测开和开发的职业路径完全不一样。开发的核心是业务和系统能力,测开的核心是稳定性和覆盖率,前者是往上走,后者天花板非常明显。你可以见到很多开发转测开,但你很少见到干了几年测开还能顺利转回开发的。更现实一点说,92&nbsp;的高学历如果拿来做测开,大部分时间就是在做重复性很强的杂活,这种工作对个人能力的放大效应非常弱。三年下来,你和一个双非的,甚至本科的测开差距不会太大,但你和同龄的后端、平台开发差距会非常明显。这不是努不努力的问题,是赛道问题。所谓测开简单高薪,本质上是把极少数核心测开的上限,当成了整个岗位的常态来宣传。那些工资高、技术强的测开,本身就是开发水平,只是挂了个测开的名。普通人进去,99%&nbsp;做的都是项目兜底型工作,而不是你想象中的平台开发。测开不是不能做,但它绝对不是开发的平替,也不是性价比最优解。如果你是真的不想做开发,追求稳定,那测开没问题。但如果你只是觉得测开比后端容易,还能进大厂,那我劝你冷静一点,这只是在用短期安全感换长期天花板。有92的学历,如果你连测开这些重复性工作都能心甘情愿接受,那你把时间精力用在真正的开发、系统、业务深度上,回报大概率比卷测开要高得多。想清楚再下场,别被岗位名和话术带偏了,就算去个前端客户端也是随便占坑的,测开是一个坑位很少赛道,反而大面积学历下放,不用想也能知道会是什么结果,我想各位在JAVA那里已经看到了
烤点老白薯:测测你的
点赞 评论 收藏
分享
评论
61
3
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务