链表中环的入口结点

链表中环的入口结点_牛客网

https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&tqId=11208&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

思路:无脑法,使用辅助存储空间。

def EntryNodeOfLoop(self, pHead):
    # write code here
    #遍历链表,环的存在,遍历遇见的第一个重复的即为入口节点
    tempList = []
    p = pHead
    while p:
        if p in tempList:
            return p
        else:
            tempList.append(p)
        p = p.next

思路2:快慢指针。快指针一次走两步,慢指针一次走一步,设链表起点到入口结点的长度是x1,快慢指针第一次相遇时距离入口结点的长度是x2,此时慢指针走了x1+x2,快指针走了2x1+2x2,也就是说x1+x2的长度正好是环的一圈大小的倍数。
此时让一个指针从起点出发,一个指针从相遇结点出发,都是一次走一步,当两个指针第一次相遇时恰好是在入口结点。

全部评论
(死记)快慢指针。快指针一次走两步,慢指针一次走一步, 此时让快指针回到head, 继续走, 当两个指针再次相遇时恰好是在入口结点。
1 回复 分享
发布于 2019-12-16 20:34
如果有1,2,3,4,5,6这几个节点,2和6首位相连算不算存在环?
点赞 回复 分享
发布于 2020-05-11 17:50
环不一定首位相连呀
点赞 回复 分享
发布于 2020-02-27 16:24

相关推荐

Yki_:你要算时间成本呀,研究生两三年,博士三四年,加起来就五六年了,如果你本科去腾讯干五年,多领五年的年薪,加上公司内涨薪,可能到时候十五年总薪资也跟博士差不多
点赞 评论 收藏
分享
MinJerous:虽然我一直说 计算机不怎么卡学历 但是至少得一本
点赞 评论 收藏
分享
评论
10
收藏
分享

创作者周榜

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