文档章节

【leetcode82】Linked List Cycle

fengsehng
 fengsehng
发布于 2016/11/09 09:12
字数 242
阅读 0
收藏 0
点赞 0
评论 0

题目描述:

判断有序list是不是环

要求:

时间复杂度o(n)

原文描述:

Given a linked list, determine if it has a cycle in it.

Follow up:

Can you solve it without using extra space?

思路:

  • 设置两个指针,一个快指针,每次走两步,一个慢指针,每次走一步
  • 如果块指针==慢指针,那么包含环
  • 注意判断空值和长度为一的情况
    -

代码:

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) {
            return false;
        }

        ListNode fast = head;
        ListNode slow = head;

        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) {
                return true;
            }
        }

        return false;
    }
}

更多leetcode题目,请看我的leetcode专栏。链接如下:

leetcode专栏

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧,都是干货!

微信订阅号二维码如下:

这里写图片描述

© 著作权归作者所有

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
LeetCode目录。

按照LeetCode的Tags来区分的话,目前共有34个Tag,只列出已经解决的题,各分类中按照题目编号排序: Linked List。 Solved:21/28 Array。

Leafage_M ⋅ 2017/11/21 ⋅ 0

怎样应对IT面试与笔试-(十五)

Linked List 链表 141. Linked List Cycle 判断单链表中是否有环 使用到的数据结构:List 使用到的算法技巧:Tow Pointers 辅助指针 这道题目同样也可以用哈希表 160. Intersection of Two L...

Ice_Frog ⋅ 05/30 ⋅ 0

leetcode- Linked List Cycle

Given a linked list, determine if it has a cycle in it. Follow up: Can you solve it without using extra space? /** * Definition for singly-linked list. * struct ListNode { * int......

thoresa ⋅ 2015/11/07 ⋅ 0

单链表中有环II

原题   Given a linked list, return the node where the cycle begins. If there is no cycle, return null.   Follow up:   Can you solve it without using extra space? 题目大意 ......

一贱书生 ⋅ 2016/12/23 ⋅ 0

环检测算法(Floyd's Tortoise and Hare)

Cycle Detect 环检测算法常用检测链表是否有环,如果有环,给出环的长度和环的入口点。 相关题目: 287. Find the Duplicate Number,141. Linked List Cycle,142. Linked List Cycle II 参考...

有苦向瓜诉说 ⋅ 2017/12/12 ⋅ 0

单链表中有环

原题   Given a linked list, determine if it has a cycle in it.   Follow up:   Can you solve it without using extra space? 题目大意   给定一个单链表,判断链表是否有环。 ...

一贱书生 ⋅ 2016/12/23 ⋅ 0

决战Leetcode: easy part(1-50)

本博客是个人原创的针对leetcode上的problem的解法,所有solution都基本通过了leetcode的官方Judging,个别未通过的例外情况会在相应部分作特别说明。 欢迎互相交流! email: tomqianmaple@...

qq_32690999 ⋅ 01/25 ⋅ 0

leetcode算法题解(Java版)-7-循环链表

一、循环链表 题目描述 Given a linked list, determine if it has a cycle in it. Follow up: Can you solve it without using extra space? 思路 不能用多余空间,刚开始没有考虑多个指针什...

kissjz ⋅ 05/03 ⋅ 0

【刷题】Linked List Cycle II

原题戳我 题目 Description Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Example Given -21->10->4->5, tail connects to node ind......

monkeysayhi ⋅ 2017/10/17 ⋅ 0

Linked List Cycle II

题目: https://oj.leetcode.com/problems/linked-list-cycle-ii/ 这一题的细节真是魔鬼。而且,好像没什么一般性,感觉就是一个智力游戏 首先, 设两个指针, s(慢指针) 和 f(快指针), s每次走...

m2012 ⋅ 2014/05/31 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

从 Confluence 5.3 及其早期版本中恢复空间

如果你需要从 Confluence 5.3 及其早期版本中的导出文件恢复到晚于 Confluence 5.3 的 Confluence 中的话。你可以使用临时的 Confluence 空间安装,然后将这个 Confluence 安装实例升级到你现...

honeymose ⋅ 今天 ⋅ 0

用ZBLOG2.3博客写读书笔记网站能创造今日头条的辉煌吗?

最近两年,著名的自媒体网站今日头条可以说是火得一塌糊涂,虽然从目前来看也遇到了一点瓶颈,毕竟发展到了一定的规模,继续增长就更加难了,但如今的今日头条规模和流量已经非常大了。 我们...

原创小博客 ⋅ 今天 ⋅ 0

MyBatis四大核心概念

本文讲解 MyBatis 四大核心概念(SqlSessionFactoryBuilder、SqlSessionFactory、SqlSession、Mapper)。 MyBatis 作为互联网数据库映射工具界的“上古神器”,训有四大“神兽”,谓之:Sql...

waylau ⋅ 今天 ⋅ 0

以太坊java开发包web3j简介

web3j(org.web3j)是Java版本的以太坊JSON RPC接口协议封装实现,如果需要将你的Java应用或安卓应用接入以太坊,或者希望用java开发一个钱包应用,那么用web3j就对了。 web3j的功能相当完整...

汇智网教程 ⋅ 今天 ⋅ 0

2个线程交替打印100以内的数字

重点提示: 线程的本质上只是一个壳子,真正的逻辑其实在“竞态条件”中。 举个例子,比如本题中的打印,那么在竞态条件中,我只需要一个方法即可; 假如我的需求是2个线程,一个+1,一个-1,...

Germmy ⋅ 今天 ⋅ 0

Springboot2 之 Spring Data Redis 实现消息队列——发布/订阅模式

一般来说,消息队列有两种场景,一种是发布者订阅者模式,一种是生产者消费者模式,这里利用redis消息“发布/订阅”来简单实现订阅者模式。 实现之前先过过 redis 发布订阅的一些基础概念和操...

Simonton ⋅ 今天 ⋅ 0

error:Could not find gradle

一.更新Android Studio后打开Project,报如下错误: Error: Could not find com.android.tools.build:gradle:2.2.1. Searched in the following locations: file:/D:/software/android/andro......

Yao--靠自己 ⋅ 昨天 ⋅ 0

Spring boot 项目打包及引入本地jar包

Spring Boot 项目打包以及引入本地Jar包 [TOC] 上篇文章提到 Maven 项目添加本地jar包的三种方式 ,本篇文章记录下在实际项目中的应用。 spring boot 打包方式 我们知道,传统应用可以将程序...

Os_yxguang ⋅ 昨天 ⋅ 0

常见数据结构(二)-树(二叉树,红黑树,B树)

本文介绍数据结构中几种常见的树:二分查找树,2-3树,红黑树,B树 写在前面 本文所有图片均截图自coursera上普林斯顿的课程《Algorithms, Part I》中的Slides 相关命题的证明可参考《算法(第...

浮躁的码农 ⋅ 昨天 ⋅ 0

android -------- 混淆打包报错 (warning - InnerClass ...)

最近做Android混淆打包遇到一些问题,Android Sdutio 3.1 版本打包的 错误如下: Android studio warning - InnerClass annotations are missing corresponding EnclosingMember annotation......

切切歆语 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部