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

  链表在面试中出现的频率很高,有的比较正常,考链表的常规操作,主要看基本功是否扎实,有些就比较难,难在思维的改变和是否能够想到对应的点。这里出现的是其中一个题目,我称之为有环链表问题。也就是从判断一个单链表是否存在循环而扩展衍生的问题。下面来看问题如何解决。   首先来看最基本的这个问题:如何判断一个单链表是否存在循环,链表数目未知。算法不能破坏链表。

思路一:哈希表法

将所有的遍历过的节点用哈希表存储起来,用节点的内存地址作为哈希表的值存储起来。每遍历一个节点,都在这个结构中查找是否遍历过。如果找到有重复,则说明该链表存在循环。如果直到遍历结束,则说明链表不存在循环。哈希表中存储的值为节点的内存地址,这样查找的操作所需时间为O(1),遍历操作需要O(n),hash表的存储空间需要额外的O(n)。所以整个算法的时间复杂度为O(n),空间复杂度为O(n)。

思路二:反转指针法

这种比较特别,是使用反转指针的方法,每过一个节点就把该节点的指针反向。当有环的时候,最后指针会定位到链表的头部,如果到最后,都没有再到头部,那说明链表不存在循环。这个方法会破坏掉链表,所以如果要求是不能破坏链表的话,我们最后就还需要反转一下,再将链表恢复(题目说不能破坏环,那我破坏之后恢复原样也算没破坏环呀。哈哈,思路不要被局限住了)。这个方法使用的空间复杂度为O(1),其实是使用了3个指针,用于进行反转。同时,时间复杂度为O(n)。

思路三:快慢指针(是错的!)

首先我们要理解什么是快慢指针。快指针pf(f就是fast的缩写)每次移动2个节点,慢指针ps(s为slow的缩写)每次移动1个节点,如果快指针能够追上慢指针,那就说明其中有一个环,否则不存在环。

这个方法的时间复杂度为O(n),空间复杂度为O(1),实际使用两个指针。

想像一种情况,当快指针走到一个环的时候,慢指针还离快指针很远,甚至当快指针走出环的时候慢指针还没到达环,这时候快指针永远不会追上慢指针。所以快慢指针无法解决链表存在循环的问题,快慢指针能解决的只是链表存在环的问题,也就是这个循环在链表尾部。可以说链表存在环是链表存在循环的一种特殊情况。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏向治洪

Java泛型和通配符那点事

泛型(Generic type 或者generics)是对 Java 语言的类型系统的一种扩展,以支持创建可以按类型进行参数化的类。可以把类型参数看作是使用参数...

24750
来自专栏liulun

Nim教程【九】

向关注这个系列的朋友们,道一声:久违了! 它并没有被我阉掉,他一定会得善终的,请各位不要灰心 Set集合类型 为了在特殊场景下提高程序的性能设置了Set类型,...

216100
来自专栏老马说编程

(29) 剖析String / 计算机程序的思维逻辑

上节介绍了单个字符的封装类Character,本节介绍字符串类。字符串操作大概是计算机程序中最常见的操作了,Java中表示字符串的类是String,本节就来详细...

20850
来自专栏用户2442861的专栏

java MS之泛型

http://blog.csdn.net/stypace/article/details/42102567

11420
来自专栏Phoenix的Android之旅

重构 - 你为什么要对参数赋值?

对于学过多门语言的开发者来说,应该都明白在不同语言中对参数赋值有着不同的意义, 总的来说参数有值传递和引用传递两种, 而在Java中只有值传递的概念。

9720
来自专栏个人随笔

房上的猫:楼主错题:解析

本题考查的是对java中数组的相关知识, 数组一旦定义就不能改变大小了;数组中存放的都是同一类型的数据;数组的下标是从0开始的,也就是说下标为0的位置存放的是第...

413110
来自专栏前端那些事

强大的原型和原型链

前两次总结了JavaScript中的基本数据类型(值类型<引用类型>,引用类型<复杂值>)以及他们在内存中的存储,对内存空间有了一个简单的了解,以及第二次总结了...

221100
来自专栏Bingo的深度学习杂货店

Q14 Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of st...

38680
来自专栏专注 Java 基础分享

Java 内部类的意义及应用

众所周知,我们的 C++ 程序语言是多继承制的,而多继承明显的好处就是,相对而言只需要写较少的代码即可完成一个类的定义,因为我们可以通过继承其它类来获取别人的实...

34840
来自专栏mukekeheart的iOS之旅

final、finally、finalize的区别

final:修饰符,可以用于修饰成员、方法和类。 如果一个类被声明为final,意味着该类不能再派生出新的子类,不能作为父类被继承。因此一个类不能即被声明为ab...

25150

扫码关注云+社区

领取腾讯云代金券