文档章节

【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
【算法分析】如何理解快慢指针?判断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
10/23
0
0
怎样应对IT面试与笔试-(十五)

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

Ice_Frog
05/30
0
0
[算法][LeetCode] 链表

[算法][LeetCode]Linked List Cycle & Linked List Cycle II——单链表中的环 1.判断链表中是否有环 2.如果有环,找出环的起点 http://www.cnblogs.com/hiddenfox/p/3408931.html 1.快慢指针...

素雷
2017/10/19
0
0
141. Linked List Cycle - LeetCode

Question 141. Linked List Cycle Solution 题目大意:给一个链表,判断是否存在循环,最好不要使用额外空间 思路:定义一个假节点fakeNext,遍历这个链表,判断该节点的next与假节点是否相等...

yysue
07/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

pyhanlp 停用词与用户自定义词典功能详解

hanlp的词典模式 之前我们看了hanlp的词性标注,现在我们就要使用自定义词典与停用词功能了,首先关于HanLP的词性标注方式具体请看HanLP词性标注集。 其核心词典形式如下: 自定义词典 自定义...

左手的倒影
26分钟前
1
0
颜色模型和颜色应用---CMY和CMYK颜色模型

CMY参数 CMY颜色空间和RGB颜色空间之间的转换

中国龙-扬科
34分钟前
3
0
Golang通道的无阻塞读写的方法示例

无论是无缓冲通道,还是有缓冲通道,都存在阻塞的情况,但其实有些情况,我们并不想读数据或者写数据阻塞在那里,有1个唯一的解决办法,那就是使用select结构。 这篇文章会介绍,哪些情况会存...

kaixin_code
35分钟前
2
0
Web登录中的信心安全问题

1. 一个简单的HTML例子看看用户信息安全 标准的HTML语法中,支持在form表单中使用<input></input>标签来创建一个HTTP提交的属性,现代的WEB登录中,常见的是下面这样的表单: <form action ...

开元中国2015
40分钟前
1
0
Hbulider打包iOS遇到的一些坑

video 全屏播放问题 在 manifest.json 的代码视图中,plus 值需加入 "allowsInlineMediaPlayback": true,如下,允许ios不进行全屏播放 "plus": { "allowsInlineMediaPlayback": true} ...

林梓阳
40分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部