文档章节

【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
怎样应对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
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
0

没有更多内容

加载失败,请刷新页面

加载更多

c++_CWinApp

CWinApp:MFC 中的主应用程序类封装用于 Windows 操作系统的应用程序的初始化、运行和终止. ON_COMMAND(ID_FILE_NEW, &CWinApp::OnFileNew)ON_COMMAND(ID_FILE_OPEN, &CWinApp::OnFileOpen...

一个小妞
3分钟前
0
0
可变对象传入set

set=([1,2,3]), 其中([ ])只是set的表现形式,并不是把list放入set中 >>> s1=set([1,2,3])>>> L[1, 2, 3]>>> s1{1, 2, 3}>>> s1(L)Traceback (most recent call last): File "<std......

fadsaa
6分钟前
0
0
多生产与多消费:操作栈

代码同“多生产与一消费”,区别在于测试类代码 public class Test { public static void main(String[] args) { MyStack myStack = new MyStack(); Produce produce......

起个昵称好难啊
7分钟前
0
0
@Component 的作用

1、@controller 控制器(注入服务) 用于标注控制层,相当于struts中的action层 2、@service 服务(注入dao) 用于标注服务层,主要用来进行业务的逻辑处理 3、@repository(实现dao访问) ...

踏破铁鞋无觅处
7分钟前
0
0
工厂模式

工厂方法模式 一个抽象产品类,可以派生出多个具体产品类。 一个抽象工厂类,可以派生出多个具体工厂类。 每个具体工厂类只能创建一个具体产品类的实例。 简单工厂模式 又称静态工厂方法模式...

noob_fly
10分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部