文档章节

【leetcode82】Linked List Cycle

fengsehng
 fengsehng
发布于 2016/11/09 09:12
字数 242
阅读 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
0
LeetCode 141. Linked List Cycle (链表环判断)

原题 Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked list, we use an integer which represents the position (0-indexed) in the li......

dby_freedom
2018/12/08
0
0
LeetCode 142. Linked List Cycle II (链表环起点)

Given a linked list, return the node where the cycle begins. If there is no cycle, return . To represent a cycle in the given linked list, we use an integer which represents the......

dby_freedom
2018/12/08
0
0
怎样应对IT面试与笔试-(十五)

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

Ice_Frog
2018/05/30
0
0
【算法分析】如何理解快慢指针?判断linked list中是否有环、找到环的起始节点位置。以Leetcode 141. Linked List Cycle, 142. Linked List Cycle II 为例Python实现

引入 快慢指针经常用于链表(linked list)中环(Cycle)相关的问题。LeetCode中对应题目分别是: 141. Linked List Cycle 判断linked list中是否有环 142. Linked List Cycle II 找到环的起始节...

rgvb178
2018/10/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

20个使用 Java CompletableFuture的例子

https://colobu.com/2018/03/12/20-Examples-of-Using-Java%E2%80%99s-CompletableFuture/

lemos
44分钟前
1
0
Apache 流框架 Flink,Spark Streaming,Storm对比分析

1.Flink架构及特性分析 Flink是个相当早的项目,开始于2008年,但只在最近才得到注意。Flink是原生的流处理系统,提供high level的API。Flink也提供 API来像Spark一样进行批处理,但两者处理...

hblt-j
48分钟前
1
0
什么是公网IP、内网IP和NAT转换?

搞网络通信应用开发的程序员,可能会经常听到外网IP(即互联网IP地址)和内网IP(即局域网IP地址),但他们的区别是什么? 1、引言 搞网络通信应用开发的程序员,可能会经常听到外网IP(即互联网I...

linuxprobe16
54分钟前
2
0
Spring Cloud搭建微服务架构----流量回放

前言 系统微服务化后,传统的自测/测试方式都变得比较困难: 依赖的服务可能不稳定。 服务无法提供期望的响应数据。 缺少场景构造标准。 随着整体业务越来越复杂,微服务依赖的越来越多,测试...

春哥大魔王的博客
今天
4
0
记一次springboot模块配置问题导致读取Apollo配置中心配置文件始终错误的问题

现在正在做的一个项目采用的是微服务,主框架是spring cloud,配置中心用的是携程的Apollo。 项目下有多个服务,在测试服务器上启动用户服务的时候发现在eureka中心另一个服务被启动了,尝试...

zcqshine
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部