LeetCode 141. Linked List Cycle (链表循环)

时间:2022-12-06 20:22:34

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 (链表循环)的更多相关文章

  1. [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 ...

  2. leetcode 141. Linked List Cycle 、 142. Linked List Cycle II

    判断链表有环,环的入口结点,环的长度 1.判断有环: 快慢指针,一个移动一次,一个移动两次 2.环的入口结点: 相遇的结点不一定是入口节点,所以y表示入口节点到相遇节点的距离 n是环的个数 w + n ...

  3. 【算法分析】如何理解快慢指针?判断linked list中是否有环、找到环的起始节点位置。以Leetcode 141. Linked List Cycle, 142. Linked List Cycle II 为例Python实现

    引入 快慢指针经常用于链表(linked list)中环(Cycle)相关的问题.LeetCode中对应题目分别是: 141. Linked List Cycle 判断linked list中是否有环 ...

  4. [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 ...

  5. 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 ...

  6. [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 ...

  7. (链表 双指针) 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 ...

  8. 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 ...

  9. LeetCode 141. Linked List Cycle(判断链表是否有环)

    题意:判断链表是否有环. 分析:快慢指针. /** * Definition for singly-linked list. * struct ListNode { * int val; * List ...

随机推荐

  1. LINUX操作系统VIM的安装和配置

    VIM的安装   在命令行敲入"vi"后按"tab"键,可以看到目前系统中只安装了vi和vim.tiny. vim是从VI发展而来的一个文本编辑器,功能更强大. ...

  2. 控件 UI: VisualState, VisualStateManager, 控件的默认 UI

    VisualState 和 VisualStateManager 控件的默认 Style, ControlTemplate, VisualState 示例1.演示“VisualState 和 Visu ...

  3. POJ1191 棋盘分割(DP)

    化简一下那个方差得到:$$\sqrt\frac{(\Sigma_{i=1}^nx_i)-n\bar x^2}{n}$$ 除了$\Sigma_{i=1}^nx_i$这部分未知,其余已知,而那部分显然越大 ...

  4. mysqldump 失败

    背景交代 mysql版本:mysql Ver 14.14 Distrib 5.7.11, for Linux (x86_64) using EditLine wrapper os:Linux vers ...

  5. (转)SQL Server 触发器

    SQL Server 触发器 触发器是一种特殊类型的存储过程,它不同于之前的我们介绍的存储过程.触发器主要是通过事件进行触发被自动调用执行的.而存储过程可以通过存储过程的名称被调用. Ø 什么是触发器 ...

  6. Http_4个新的http状态码:428、429、431、511

    1.428 Precondition Required (要求先决条件) 先决条件是客户端发送 HTTP 请求时,必须要满足的一些预设条件.一个好的例子就是 If-None-Match 头,经常用在 ...

  7. Pitch detection algorithm(基音搜索算法)PDA相关链接

    第一:* http://en.wikipedia.org/wiki/Pitch_estimation 简要系统介绍了基音估计算法的分类和一些链接,论文 第二:http://ws2.bingham ...

  8. [No0000110]Git9/9-自定义Git

    在安装Git一节中,我们已经配置了user.name和user.email,实际上,Git还有很多可配置项. 比如,让Git显示颜色,会让命令输出看起来更醒目: $ git config --glob ...

  9. mybatis 关于传long 类型问题

    @Datapublic class PrealertPackageStatusDTO { private Integer nowStatus; /** * packageStatusEnum */ p ...

  10. COGS2608 [河南省队2016]无根树

    传送门 这题大概就是传说中的动态树形DP了吧,学习了一波…… 首先,对于没有修改的情况,不难想到树形DP,定义$f_i$表示强制必须选$i$且只能再选$i$的子树中的点的最优解,易得转移方程$f_i= ...