有环链表如何高效的判断是否有环,以及在何处产生环?
采用2个指针不同步数(步数小的每次1步,步数大的每次2步),步数大的如果能够与步数小的相遇则必然存在环。
相遇后的情况如图,假设相遇后步数大的回绕环遍历了n遍,步数小的肯定一遍也没遍历完,假设第一段距离为a,第2段距离为c,第3段距离为b
则有(a+c)*2 = a+n(b+c)+c,转换后得 a = n(b+c) - c,也就是说,从出发点出发,移动a的距离,刚好等于相遇点出发移动n个整圈减c的距离,这个点刚好就是环产生的点,由此可以设置2个指针,分别从根节点与相遇点出发,第一次相遇的地方则是环产生的点。
完成证明后,代码较为简单,如下
package com.xhb.algorithms;
public class MyLinkedList {
private LinkListNode<Integer> root = new LinkListNode<Integer>(null, null);
private int length;
private int point;
/**
* @param args
*/
public static void main(String[] args) {
MyLinkedList list = new MyLinkedList(10045, 232);
System.out.println(list.isHasRound());
System.out.println("the point cut obj is " + list.getCutPoint());
}
/**
* 初始化一个环链表
*/
private MyLinkedList(int length, int point) {
this.length = length;
this.point = point;
LinkListNode<Integer> current = this.root;
for (int i = 1; i <= this.length - 1; i++) {
current = current.next(new LinkListNode<Integer>(new Integer(i),
null));
}
if (this.point < 0) {
current.next(null);
} else {
LinkListNode<Integer> pointObj = this.root;
for (int i = 0; i < point; i++) {
pointObj = pointObj.next();
}
current.next(pointObj);
}
}
public Integer getCutPoint() {
LinkListNode<Integer> seekPoint = this.getSeekPoint();
System.out.println(seekPoint.data());
LinkListNode<Integer> a = this.root;
while (true) {
a = a.next();
seekPoint = seekPoint.next();
if (a == seekPoint) {
return a.data();
}
// System.out.println(a.data() +"," + seekPoint.data());
}
}
private LinkListNode<Integer> getSeekPoint() {
LinkListNode<Integer> a = this.root;
LinkListNode<Integer> b = this.root;
a = a.next();
b = b.next().next();
while (true) {
a = a.next();
b = b.next();
if (b == null) {
return null;
}
if (a == b && b != null) {
return b;
}
b = b.next();
if (b == null) {
return null;
}
if (a == b && b != null) {
return b;
}
}
}
public boolean isHasRound() {
return this.getSeekPoint() != null;
}
}
class LinkListNode<T> {
private LinkListNode<T> next = null;
private T data;
public LinkListNode(T data, LinkListNode<T> next) {
this.data = data;
this.next = next;
}
public LinkListNode<T> next() {
return next;
}
public LinkListNode<T> next(LinkListNode<T> next) {
this.next = next;
return next;
}
public T data() {
return this.data;
}
@Override
public String toString() {
return data.toString();
}
}
- 大小: 15.9 KB
分享到:
相关推荐
用链表实现约瑟夫环,可以直接执行,编程语言为C++,适合初学者。
问题:给定一个有环的单链表,找到它的环的起始节点网上都是用快慢指针法来解的,现在对部分原理给出证明:首先证明快慢指针在环中是可以恰好相遇的:设链表的头节点为,环
LinkedGraph.h 图的父类文件 LinkedGraphDirected(with reverse func).h 有向图带邻接链表翻转...ListCircle.h 环链表 MinCostSpanningTree.h 最小生成树 MinHeap.h 最小堆 Stack.h 栈 tree.h 数 UFSets.h UFSets集合
this file is the test of the single linked-list and double linked-list take care that each node in the list have a key id, the node with same key id can only be added once,before one node is added,the...
数据结构实验,用一个链表解法实现约瑟夫环
从实际应用出发重新定义线性链表及其基本操作,从新定义的链表结构更加直观,节俭,易懂,思路清晰。 从编写底层驱动的思路来编写了库,整个编写只为实现简单的链表结构代码,对于程序员来说,编写驱动要对用户...
数据结构的课设,瑟夫环,通过简单的输入设置,来设定开始位置,报数大小,从而不断将报到的人移除
Linux运维-嵌入式物联网开发教程-有头双向环链空链表创建.mp4
2、 约瑟夫(Josephus)环问题:编号为1,2,3,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止。报m...
判断两个有环链表是否相交,相交则返回第一个相交节点,否则返回null 在考虑此问题时,根据前面几篇文章的解法,我们已经得到了各自链表的入环节点,分别为loop1和loop2 思路 以下是问题三的具体解决过程: 如果loop...
环链葫芦操作维护手册 , 型号为ST05,ST10,ST20,ST30,ST32,ST50和ST60的环链葫芦可以应. 用于不同形式的电气设备.环链葫芦运行时有危险的电压.
自己编写得约瑟夫环,有需要得做数据结构得可以下载来看看
Linux运维-嵌入式物联网开发教程-一维数组传参.mp4
链表相关问题的完整代码,包括测试类和关键代码: **0、将链表翻转** **1、判断链表是否有环** **2、寻找环的入口点** **3、计算环的节点数** ...**6、判断两个无环链表是否相交** **7、寻找两个链表的相交的节点**
通过1 H和13 C NMR光谱表明,脂族和芳族醛的2-巯基苯甲酰-以线性和环状苯并-1,3,4-噻二氮杂形式的互变异构混合物形式存在于溶液中。 线性形式由(E,E')-和(E,Z')-构象异构体表示,相对于酰胺C–N键的位置不同。...
矿用圆环链的生产工序主要包括下料、编环、焊接、热处理、拉伸等几道工序。在生产过程中,焊接、热处理是矿用圆环链的关键工序,直接影响产品质量。依据产品标准、生产工艺及实践经验,重点讨论焊接和热处理2个方面,...
Linux运维-嵌入式物联网开发教程-有头双向环链概念.mp4
Linux运维-嵌入式物联网开发教程-有头双向环链新增结点.mp4
Linux运维-嵌入式物联网开发教程-有头双向环链的删除.mp4