创建一个ArrayList,若新的结点不在List中,则加入List,在其中的话,返回该结点

链表中环的入口节点

http://www.nowcoder.com/questionTerminal/6e630519bf86480296d0f1c868d425ad

用java解决还是很好的,创建一个ArrayList,若新的结点不在List中,则加入List,在其中的话,返回该结点 就是入口了

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ArrayList<ListNode> arr = new ArrayList<>();
        ListNode l = head;
        while(l!=null){
            if(arr.contains(l)){
                return l;
            }else{
                arr.add(l);
            }
            l = l.next;
        }
        return null;
    }
全部评论
题目说了不能增加新空间呢.
点赞 回复 分享
发布于 2021-01-11 15:26
面试的时候我就这么说的,然后就被刷啦 嘻嘻
点赞 回复 分享
发布于 2021-01-29 13:34

相关推荐

03-15 20:26
已编辑
电子科技大学 C++
T3题面:给一个3e5数组,每次询问长度为len的子数组乘积的和,如果子数组乘积&gt;1e9,则视为0.赛后一分钟想出来了,比赛时打了个暴力+线段树注意到1e9大约是2^30,&nbsp;因此len长度如果&gt;30就直接输出0,30以内做一个记忆化就行,复杂度O(30*n)感觉是以前比赛做过的题,忘了怎么做了。。。---upd:&nbsp;忘了数据范围了,如果有0,1的话那这样也不行
blueswiller:给出一个做法,刚刚才想到,应该没问题,时间复杂度为 O(max(30n, nlogn)): 1. 根据 0 切分数组。2. 现在问题转化为>=1 的情况,我们首先维护每一个数前一个 > 1 的数的位置,同时维护一个长度的差分数组,初始值全为 0。3. 我们从每一个数 i 开始向前跳,至多跳 30 次,维护这个过程中的乘积,于是得到 30 个区间加和。举例:假设从 j1 跳到 j2 ,相当于对查询长度 (i- j1 + 1) 至 (i - j2) 贡献 a_i * ... * a_j1。4. 对于所有区间加和,我们采用差分数组结合树状数组对其进行维护,由于长度至多为 n ,树状数组构建的复杂度为 O(nlogn),于是,构建阶段的复杂度为 O(max(30n, nlogn))。在线单次查询的复杂度为树状数组查询的复杂度 O(logn)。
投递淘天集团等公司10个岗位 > 笔试
点赞 评论 收藏
分享
03-14 11:58
门头沟学院 Java
腾讯暑期实习java选手,完全不懂C++,貌似游戏行业都是用C++的而且天美好像在成都,个人比较想去上海或深圳
siestaaaaaa:天美不止在成都,深圳上海都有。 游戏服务器也不全是cpp,至少我们项目是java ,但是工作中什么语言都会用到,比如cpp、lua、py等等,语言本身其实不重要
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务