【题目】
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;
}
};
分享到:
相关推荐
终生成长 :hot_beverage: 为什么要建这个仓库 梳理自己掌握的知识点,整理自己的知识体系。... Reverse Linked ListLeetcode 141. Linked List CycleLeetcode 21. Merge Two Sorted ListsLeetCode 224. Basic Cal
leetcode中文版 LeetCode/Cpp 本人刷题记录在此,包含题意理解与算法思路,包含在Cpp文件内部注释,后续会持续更新。 有不懂的可以联系ji648513181,同时也欢迎志同道合O的朋友一起合作更新。 已更新剑指Offer答案...
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.com 的 Java 答案 ================索引================ com.leetcode.array Search a 2D Matrix Spiral Matrix com.leetcode.list Linked List Cycle Linked List Cycle II ...
* [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...
https://leetcode.com/problems/linked-list-cycle/ https://leetcode.com/problems/merge-two-sorted-lists/ 2D阵列 https://leetcode.com/problems/spiral-matrix/ ...
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
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 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便签 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? 解决思路 声明一个慢指针和一个快...
141.Linked-List-Cycle │ ├── solution.cpp │ ├── solution.go │ └── solution.md [ -> Explain thoughts about this problem.] ├── 404.Sum-of-Left-Leaves │ ├── solution.cpp │ ├...
leetcode中325题python leetcode 以 参考 和 Hash相关 1_两数之和 ...linked-list-cycle-ii 143 重排链表 reorder-list 148 排序链表 sort-list 234 回文链表 palindrome-linked-list 双指针遍历/滑动
linked-list-cycle/Solution.993783.java $ tree . ├── add-binary │ └── Solution.665166.java ├── add-two-numbers │ └── Solution.666385.java ├── balanced-binary-tree │ └── ...
leetcode 2 sum c LeetCode 贵有恒,何必三更起五更睡;最无益,只怕一日暴十寒。 我的个人网站: 分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类...Cycle 160 * Intersection of Two Linke
leetcode 2 sum c LeetCode 贵有恒,何必三更起五更睡;最无益,只怕一日暴十寒。 我的个人网站: 分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类...Cycle 160 * Intersection of Two Linke
java二叉树算法源码 algorithm-primer algorithm primer - 算法基础、Leetcode编程、剑指offer 目录 Leetcode编程 ...141 判断链表是是否存在环 Linked List Cycle Easy 142 环形链表II Linked List Cycle I
leetcode 答案Leet Code 挑战 这是我提交给 Lambda School CS Unit 2 构建周的已接受 ...如果您想自己尝试,这些链接将带您进入代码挑战。...要查看我接受的答案,只需转到与...[Linked List Cycle II](https://leetcode.co
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 其中算法,主要...
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动态规划
141-环形链表:linked-list-cycle 142-环形链表:linked-list-cycle-ii 160-相交链表:intersection-of-two-linked-lists 206-反转一个单链表:reverse-linked-list 20-有效的括号:valid-parentheses 150-逆波兰表达式求...