JavaScript判断单链表中是否存在环

binta 发布于2019-08-26 13:33 / 2437人阅读

摘要：如下图单链表中存在环怎么判断单链表中存在环呢先创造一下带环的单链表代码如下创建带环单链表结果可见判断单链表是否带环以下有三种方法第一种方法创建哈希表不过会占用较大的空间不是最佳方法时间复杂度遍历链表将链表各节点添加至哈希表中添加前判断此节点

如下图, 单链表中存在环:

怎么判断单链表中存在环呢?先创造一下带环的单链表:

代码如下:

创建带环单链表:

结果可见:

判断单链表是否带环,以下有三种方法:
第一种方法, 创建哈希表,不过会占用较大的空间,不是最佳方法.( 时间复杂度O(n) )

遍历链表,将链表各节点添加至哈希表中,添加前判断此节点是否已存在哈希表中,存在的话说明链表中存在环.

结果如下:

检测到节点B是重复项,说明存在环

第二种方法: 给节点添加visited访问标记 (时间复杂度O(n)), 不需要额外的空间

遍历链表,每访问一个新节点,使其visited为1,每次访问节点前先判断其visited是否为1,为1则是已访问过的节点,说明链表中存在环.

结果可见:

遍历链表前,链表每个节点visited都为0,都没被访问过

B节点的visited为1,说明已访问过B,链表中存在环

遍历后,链表中每个节点visited都为1,每个节点都被访问过

第三种方法: 快慢指针法,设定快指针fast,慢指针slow,每次循环快指针fast移动两个位置,慢指针移动一个位置
(时间复杂度 O(n)) 需要额外的空间

结果可见:

快指针fast和慢指针slow在节点D相遇,说明链表中存在环

原理如下图:

GPU云服务器云服务器判断session是否存在 python判断文件是否存在 mysql 判断数据库是否存在是否存在

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/109038.html

LeetCode 之 JavaScript 解答第142题 —— 环形链表 II（Linked Li

摘要：说明不允许修改给定的链表。算法思路题目要求返回单链表中存在循环链表的位置。首先，先判断该单链表是否存在循环链表用两个快慢指针分别指向链表的头部，每次移动两步，每次移动一步，移动的步数是的两倍。 Time：2019/4/8Title: Linked List Cycle IIDifficulty: mediumAuthor:小鹿题目：Linked List Cycle II Giv...

whidy 2019-08-23 16:51 评论0 收藏0
JAVASCRIPT算法（6）

摘要：还是链表算法题目描述给出两个无环单链表判断和是否相交。所以可以得出另外一种解法，先遍历链表，记住尾节点，然后遍历链表，比较两个链表的尾节点，如果相同则相交，不同则不相交。想法还是奇妙的。算法写起来不难，难的是想到这个。还是链表算法题目描述：给出两个无环单链表A: a1 → a2 ↘ c1 → c2 → c3 → ...

FreeZinG 2019-08-21 17:56 评论0 收藏0
写一段代码判断单向链表中有没有形成环，如果形成环，请找出环的入口处，即P点

摘要：由于要比移动的快，如果有环，一定会先进入环，而后进入环。现在问题就简单了，由于移动的距离永远是的一般，因此当遍历玩整个环长度个节点的时候正好遍历了个节点，也就是说，此时正好指向距离最远的点。首先，关于单链表中的环，一般涉及到以下问题： 1.给一个单链表，判断其中是否有环的存在； 2.如果存在环，找出环的入口点； 3.如果存在环，求出环上节点的个数； 4.如果存在环，求出链表的长度； ...

OldPanda 2019-07-01 13:56 评论0 收藏0
我的面试准备过程--链表(更新中)

摘要：拿了小米和美团的，要被延期，失效，工作重新找。把准备过程纪录下来，共勉。注意，有环的链表，此种方法失效。已知两个单链表和各自有序，把它们合并成一个链表依然有序写在最前面导师贪腐出逃美国，两年未归，可怜了我。拿了小米和美团的offer，要被延期，offer失效，工作重新找。把准备过程纪录下来，共勉。链表是最常考察的数据结构 // 链表定义 public class Node{ ...

30e8336b8229 2019-08-16 10:36 评论0 收藏0