单向链表,只能访问next元素,如何判断是否存在环?
最简单的方案,不考虑空间复杂度,我们会想到使用一个Set来保存集合,用来记录已经访问过的元素…
/** * 最简单的算法,但需要的空间比较高,一个Set集合 * @param link * @param <T> * @return */ public static <T> boolean containsCircle1(Link<T> link) { if(link == null){ return false; } T value = link.getValue(); Set<T> values = new HashSet<T>(); values.add(value); while ((link = link.getNext()) != null){ if(link == null){ return false; } value = link.getValue(); if (values.contains(value)) { return true; } } return false; }
这会浪费O(n)的空间,效率低下,如果链表长度过长,占用的空间会非常大,考虑一下有无其他简便的方法?
使用两个指针,分别以不同的速度向前遍历,一个以单个元素为步长,另一个以两个元素为步长,如果两个元素步长的指针追上了后面的指针,这便证明该链表中存在环。这样,只需要额外的两个空间,空间复杂度为O(1)。
/** * 使用两个指针,一个以速度1前进,另一个以速度2前进,如果存在闭环,则必定会出现交叉碰面 * @param link * @param <T> * @return */ public static <T> boolean containsCircle2(Link<T> link) { if (link == null || link.getNext() == null) { return false; } Link<T> first = link; Link<T> second = link.getNext(); while (second != null && second.getNext() != null && second.getNext().getNext() != null) { first = first.getNext(); second = second.getNext().getNext(); if (first.getValue() == second.getValue()) { return true; } } return false; }
相关推荐
C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表
04.单向链表以及单向链表的应用.ppt
C#单向链表的实现的源码
c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,
单向链表架构代码,适合学习链表的学生学习!内附排序函数,打印函数,链表尾添项函数,删除函数。
1.随机产生或键盘输入一组元素,建立一个带头结点的单向链表(无序)。 2.遍历单向链表。 3.把单向链表中元素逆置(不允许申请新的结点空间)。 4.在单向链表中删除所有的偶数元素结点。 5.编写在非递减...
这是一个单向链表,它具有插入与删除节点的功能。Entry类实现了链表的各节点。
Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现...
将一个单向链表反向连接
本文件描述单向链表类模板。移植时,仅需要本文件
培训班老师自己写的单向链表,代码非常全,也很好理解,可执行。
单向链表类定义及测试文件 对应于数据机构与算法分析(c++版)第三版或第二版 作者Clifford A.Shaffer 重庆大学使用教材
数据结构,c语言实现的单向链表。代码分享 struct LinkNode { int data; struct LinkNode *next; }; typedef struct LinkNode *Lnode;
C++进阶学习——单向链表的实现,相关教程链接如下: http://blog.csdn.net/tennysonsky/article/details/49685199
java语言模拟单向链表,JAVA数据结构
C 语言版 单向链表 #include #include typedef struct student { int num; struct student *next; }st; st *creat() //创建链表 { st *head , *tail , *p; int num = 0; head = tail = p = NULL; printf...
slist.h为单向链表,blist为双向链表
数据结构实验报告,使用vC++ 6.0工具来进行调试单向链表。
很好的一个说明了单向链表的操作方法 创建
使用单向链表对字符串进行排序,并以从小到大的顺序显示出来。