`
SunnyYoona
  • 浏览: 361463 次
社区版块
存档分类
最新评论

[LeetCode]141.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?

【题意】

给定一个链表,确定它是否包含一个环。

【分析】

最容易想到的方法是,用一个哈希表 unordered_map<int, bool> visited,记录每个元素是否被访问过,一旦出现某个元素被重复访问,说明存在环。

空间复杂度 O(n),时间复杂度 O(N )。

最好的方法是时间复杂度 O(n),空间复杂度 O(1) 的。设置两个指针,一个快一个慢,快的指针每次走两步,慢的指针每次走一步,如果快指针和慢指针相遇,则说明有环。

【代码】

/*---------------------------------------------------------
*   日期:2015-04-23
*   作者:SJF0115
*   题目: 141.Linked List Cycle
*   网址:https://leetcode.com/problems/linked-list-cycle/
*   结果:AC
*   来源:LeetCode
*   博客:
------------------------------------------------------------*/
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head,*fast = head;
        while(fast != NULL && fast->next != NULL){
            //慢指针走一步
            slow = slow->next;
            //快指针走两步
            fast = fast->next->next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }
};



分享到:
评论

相关推荐

    tech.github.io:我的博客

    终生成长 :hot_beverage: 为什么要建这个仓库 梳理自己掌握的知识点,整理自己的知识体系。... Reverse Linked ListLeetcode 141. Linked List CycleLeetcode 21. Merge Two Sorted ListsLeetCode 224. Basic Cal

    leetcode中文版-LeetCode:力码

    leetcode中文版 LeetCode/Cpp 本人刷题记录在此,包含题意理解与算法思路,包含在Cpp文件内部注释,后续会持续更新。 有不懂的可以联系ji648513181,同时也欢迎志同道合O的朋友一起合作更新。 已更新剑指Offer答案...

    javalruleetcode-leetcode-java:力码笔记

    java lru leetcode leetcode-java leetcode刷题笔记 ...141.Linked List Cycle 142.Linked List Cycle II 188.Best Time to Buy and Sell Stock IV 217.Contains Duplicate 263.Ugly Number 264.Ugly Number II

    leetcode答案-leetcode-java:leetcode的Java代码

    leetcode 答案leetcode-java leetcode.com 的 Java 答案 ================索引================ com.leetcode.array Search a 2D Matrix Spiral Matrix com.leetcode.list Linked List Cycle Linked List Cycle II ...

    LeetCode最全代码

    * [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...

    recommended-problems

    https://leetcode.com/problems/linked-list-cycle/ https://leetcode.com/problems/merge-two-sorted-lists/ 2D阵列 https://leetcode.com/problems/spiral-matrix/ ...

    leetcode2sumc-LeetCode:LeetCode的一些题目

    leetcode 2 sum c LeetCode 帮助文档 ...Cycle 160 Easy Intersection of Two Linked Lists 203 Easy Remove Linked List Elements no 206 Easy Reverse Linked List 234 Easy Palindrome Linked List

    lrucacheleetcode-LeetCode:LeetCode刷题

    leetcode LeetCode 剑指offer LeetCode解题记录(python) 2018.9.19 两数之和(Two Sum) 2018.9.19 两数相加(Add Two Numbers) 2018.9.25 翻转二叉树(Invert Binary Tree) 2018.9.25 环形链表(Linked List ...

    leetcode不会-Leetcode-Java:Leetcode-Java

    leetcode 不会 Leetcode Solutions in Java Linked List Linked List Cycle Given a linked list, determine if it has a cycle in it. public static boolean hasCycle(ListNode head) 快慢指针法,块指针从head....

    leetcode怎么销号-LeetCode-Top-Interview-Questions:LeetCode-Top-Interview-Qu

    leetcode怎么销号 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? 解决思路 声明一个慢指针和一个快...

    leetcode分类-LeetCodeJourney:保持练习

    141.Linked-List-Cycle │  ├── solution.cpp │  ├── solution.go │  └── solution.md [ -&gt; Explain thoughts about this problem.] ├── 404.Sum-of-Left-Leaves │  ├── solution.cpp │  ├...

    leetcode中325题python-leetcode:leetcode

    leetcode中325题python leetcode 以 参考 和 Hash相关 1_两数之和 ...linked-list-cycle-ii 143 重排链表 reorder-list 148 排序链表 sort-list 234 回文链表 palindrome-linked-list 双指针遍历/滑动

    leetcode和oj-leetcode_downloader:用于您已接受的leetcodeoj提交的下载器

    linked-list-cycle/Solution.993783.java $ tree . ├── add-binary │  └── Solution.665166.java ├── add-two-numbers │  └── Solution.666385.java ├── balanced-binary-tree │  └── ...

    leetcode2sumc--Offer:-提供

    leetcode 2 sum c LeetCode 贵有恒,何必三更起五更睡;最无益,只怕一日暴十寒。 我的个人网站: 分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类...Cycle 160 * Intersection of Two Linke

    leetcode2sumc-ack-CherishLeetCode:ack-CherishLeetCode

    leetcode 2 sum c LeetCode 贵有恒,何必三更起五更睡;最无益,只怕一日暴十寒。 我的个人网站: 分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类...Cycle 160 * Intersection of Two Linke

    java二叉树算法源码-algorithm-primer:algorithmprimer-算法基础、Leetcode编程和剑指offer,Ja

    java二叉树算法源码 algorithm-primer algorithm primer - 算法基础、Leetcode编程、剑指offer 目录 Leetcode编程 ...141 判断链表是是否存在环 Linked List Cycle Easy 142 环形链表II Linked List Cycle I

    leetcode答案-code_challenges:代码挑战

    leetcode 答案Leet Code 挑战 这是我提交给 Lambda School CS Unit 2 构建周的已接受 ...如果您想自己尝试,这些链接将带您进入代码挑战。...要查看我接受的答案,只需转到与...[Linked List Cycle II](https://leetcode.co

    leetcode卡-leetcode:利特码解决方案

    Cycle trees Convert Sorted Array to Binary Search Tree string and search First Bad Version Dynamic Programing *** Climbing Stairs Set Matrix Zeroes API System.arrayCopy 刷题顺序 TOP100 其中算法,主要...

    LeetCode:LeetCode解决方案

    preorder-traversal链表reorder-list链表linked-list-cycle-ii链表linked-list-cycle动态规划word-break-ii动态规划word-break链表copy-list-with-random-pointer复杂度single-number-ii复杂度single-number动态规划

    leetcode分发糖果-ForDaFactory:使用C++的个人leetcode解决方案

    141-环形链表:linked-list-cycle 142-环形链表:linked-list-cycle-ii 160-相交链表:intersection-of-two-linked-lists 206-反转一个单链表:reverse-linked-list 20-有效的括号:valid-parentheses 150-逆波兰表达式求...

Global site tag (gtag.js) - Google Analytics