Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
题目标签:Linked List
题目给了我们一个 Linked List,让我们判断它是否循环。
利用快,慢指针,快指针一次走2步,慢指针一次走1步,如果循环,快慢指针一定会相遇。
Java Solution:
Runtime beats 98.15%
完成日期:06/09/2017
关键词:singly-linked list;cycle
关键点:fast, slow pointers
/**
* 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)
return false; ListNode slow = head;
ListNode fast = head; do
{
if(fast.next == null || fast.next.next == null) // if fast reaches to end, it doens't have a cycle
return false; fast = fast.next.next; // fast moves 2 steps
slow = slow.next; // slow moves 1 step } while(fast != slow); return true; // if fast catches slow, meaning it has a cycle
}
}
参考资料:N/A
LeetCode 题目列表 - LeetCode Questions List
题目来源:https://leetcode.com/
LeetCode 141. Linked List Cycle (链表循环)的更多相关文章
-
[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 ext ...
-
leetcode 141. Linked List Cycle 、 142. Linked List Cycle II
判断链表有环,环的入口结点,环的长度 1.判断有环: 快慢指针,一个移动一次,一个移动两次 2.环的入口结点: 相遇的结点不一定是入口节点,所以y表示入口节点到相遇节点的距离 n是环的个数 w + n ...
-
【算法分析】如何理解快慢指针?判断linked list中是否有环、找到环的起始节点位置。以Leetcode 141. Linked List Cycle, 142. Linked List Cycle II 为例Python实现
引入 快慢指针经常用于链表(linked list)中环(Cycle)相关的问题.LeetCode中对应题目分别是: 141. Linked List Cycle 判断linked list中是否有环 ...
-
[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 lis ...
-
LeetCode 141. Linked List Cycle 判断链表是否有环 C++/Java
Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked lis ...
-
[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 ext ...
-
(链表 双指针) 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 lis ...
-
LeetCode 141. Linked List Cycle环形链表 (C++)
题目: Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked ...
-
LeetCode 141. Linked List Cycle(判断链表是否有环)
题意:判断链表是否有环. 分析:快慢指针. /** * Definition for singly-linked list. * struct ListNode { * int val; * List ...
随机推荐
-
LINUX操作系统VIM的安装和配置
VIM的安装 在命令行敲入"vi"后按"tab"键,可以看到目前系统中只安装了vi和vim.tiny. vim是从VI发展而来的一个文本编辑器,功能更强大. ...
-
控件 UI: VisualState, VisualStateManager, 控件的默认 UI
VisualState 和 VisualStateManager 控件的默认 Style, ControlTemplate, VisualState 示例1.演示“VisualState 和 Visu ...
-
POJ1191 棋盘分割(DP)
化简一下那个方差得到:$$\sqrt\frac{(\Sigma_{i=1}^nx_i)-n\bar x^2}{n}$$ 除了$\Sigma_{i=1}^nx_i$这部分未知,其余已知,而那部分显然越大 ...
-
mysqldump 失败
背景交代 mysql版本:mysql Ver 14.14 Distrib 5.7.11, for Linux (x86_64) using EditLine wrapper os:Linux vers ...
-
(转)SQL Server 触发器
SQL Server 触发器 触发器是一种特殊类型的存储过程,它不同于之前的我们介绍的存储过程.触发器主要是通过事件进行触发被自动调用执行的.而存储过程可以通过存储过程的名称被调用. Ø 什么是触发器 ...
-
Http_4个新的http状态码:428、429、431、511
1.428 Precondition Required (要求先决条件) 先决条件是客户端发送 HTTP 请求时,必须要满足的一些预设条件.一个好的例子就是 If-None-Match 头,经常用在 ...
-
Pitch detection algorithm(基音搜索算法)PDA相关链接
第一:* http://en.wikipedia.org/wiki/Pitch_estimation 简要系统介绍了基音估计算法的分类和一些链接,论文 第二:http://ws2.bingham ...
-
[No0000110]Git9/9-自定义Git
在安装Git一节中,我们已经配置了user.name和user.email,实际上,Git还有很多可配置项. 比如,让Git显示颜色,会让命令输出看起来更醒目: $ git config --glob ...
-
mybatis 关于传long 类型问题
@Datapublic class PrealertPackageStatusDTO { private Integer nowStatus; /** * packageStatusEnum */ p ...
-
COGS2608 [河南省队2016]无根树
传送门 这题大概就是传说中的动态树形DP了吧,学习了一波…… 首先,对于没有修改的情况,不难想到树形DP,定义$f_i$表示强制必须选$i$且只能再选$i$的子树中的点的最优解,易得转移方程$f_i= ...