如何检测链表中存在的环

链表有环的定义是,链表的尾节点指向了链接中间的某个节点。比如下图,如果单链表有环,则在遍历时,在通过结点J之后,会重新回到结点D。

看了上面的定义之后,如何判断一个单链表是否有环呢?

思路一:快慢指针

这个可以用昨天提到的“快慢指针”来解决吧?

设两个工作指针,一个快一个慢,如果有环的话,它们会必然在某点相遇。

算法的思想是设定两个指针p, q,其中p每次向前移动一步,q每次向前移动两步。那么如果单链表存在环,则p和q相遇;否则q将首先遇到null。

思路二:节点路径计算

设两个工作指针p、q,p总是向前走,但q每次都从头开始走,对于每个节点,看p走的步数是否和q一样。比如p从A走到D,用了4步,而q则用了14步。因而步数不等,出现矛盾,存在环。

以上面图片的环来说。p 总是向前走,而 q 每次都从头开始走,它们都从节点A出发。

第 1 次,p 走到 B 点,这时 p 走了 1 步。此时 q 从头开始走,走到 B 点也用了 1 步。没有问题。

第 2 次,p 走到 C 点,这时 p 走了 2 步。此时 q 从头开始走,走到 C 点也用了 1 步。没有问题。

……

第 12 次,p 走到 J 点,这时 p 走了 12 步。此时 q 从头开始走,走到 J 点也用了 12 步。没有问题。

第 13 次,p 走到 D 点, 这时 p 走了 14 步。此时 q 从头开始走,走到 D 点只用了 3 步。p 和 q 走到相同个位置上的步数不相等,说明链表存在环。

如果一直到 p == null 的时候还未出现步数不相等的情况,那么就说明不存在链表环。

思路三:标记法

可以遍历这个链表,遍历过的节点标记为Done,如果当目前准备遍历的节点为Done的时候,那么存在环,否则准备检测的节点为Null时,遍历完成,不存在环。

思路四:哈希表法

每个节点是只读的,不可以做标记呢?那可以另外开辟一个哈希表,每次遍历完一个节点后,判断这个节点在哈希表中是否存在,如果不存在则保存进去。如果存在,那么就说明存在环。要是取到Null还没有重复,那么就是不存在了。这个哈希表可以在 Java 语言中可以用 HashMap 实现。

那如何检测链表中是存在循环呢?

请看这里:如何检测链表中存在的环 - ChanShuYi - 博客园

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LintCode 数字三角形题目分析1 (常规的动态规划解法)分析2 (如果你只用额外空间复杂度O(n)的条件)

给定一个数字三角形,找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。 ** 注意事项 如果你只用额外空间复杂度O(n)的条件下完成可以获...

952
来自专栏iOS 开发杂谈

为什么数组都是从0开始编号

为什么数组都是从 0 开始编号,首先先了解一下数组的概念。 数组 Array 是一种线性表数据结构,是一组连续的内存空间,用来存储一组具有相同类型的数据。数组...

2553
来自专栏Java技术分享

泛形

一. 泛型概念的提出(为什么需要泛型)? 首先,我们看下下面这段简短的代码:

19010
来自专栏贾志刚-OpenCV学堂

TensorFlow中常量与变量的基本操作演示

TensorFlow中常量与变量的基本操作演示 本文将介绍TensorFlow中的基本算法运算与矩阵运算,介绍Tensorflow中常量、变量、操作符等基本运算...

4278
来自专栏WD学习记录

牛客网 和为S的两个数字

输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

1774
来自专栏Golang语言社区

Go语言 -浮点数

Go提供了两种size的浮点数,float32和float64。它们的算术规范是由IEEE754国际标准定义,现代CPU都实现了这个规范。 浮点数能够表示的范...

3724
来自专栏小樱的经验随笔

统计0到n之间1的个数[数学,动态规划dp](经典,详解)

问题描述 给定一个十进制整数N,求出从1到N的所有整数中出现”1”的个数。 例如:N=2时 1,2出现了1个 “1” 。 N=12时 1,2,3,4,5,6,...

3548
来自专栏计算机视觉与深度学习基础

Leetcode 282. Expression Add Operators

Given a string that contains only digits 0-9 and a target value, return all pos...

1888
来自专栏mathor

2017百度之星初赛(A):小C的倍数问题

 假设P进制下有个数(abc)~P~,若这个数满足:(abc)~P~ % B == 0,则以下两个等式一定成立:

793
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之数值的整数次方(九度OJ1514)

题目描述: 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 输入: 输入可能包含多个测试样例。 ...

2207

扫码关注云+社区

领取腾讯云代金券