`
madbluesky
  • 浏览: 84032 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论
阅读更多

有环链表如何高效的判断是否有环,以及在何处产生环?

采用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
分享到:
评论

相关推荐

    环链表问题1

    标题中的“环链表问题1”是一个典型的计算机科学问题,主要涉及数据结构中的链表以及算法设计。描述中提到了解决此类问题的常见方法——快慢指针法,这是一种高效且简洁的解决环形链表问题的策略。下面将详细阐述这...

    数据结构实验:约瑟夫环链表解法

    本次实验的主题是“数据结构实验:约瑟夫环链表解法”,这涉及到一个经典的算法问题——约瑟夫环,以及其在链表数据结构上的实现。下面将详细阐述约瑟夫环问题、环形链表的基本概念,以及如何利用链表来解决约瑟夫环...

    约瑟夫环(链表实现)

    "约瑟夫环(链表实现)" 约瑟夫环是一种经典的算法问题,它的主要思想是使用链表来模拟一个环形结构,然后通过遍历这个环形结构来实现约瑟夫环的操作。下面我们将详细介绍约瑟夫环的链表实现。 首先,我们需要定义...

    C语言带环链表.zip

    在计算机科学中,链表是一种基础且重要的数据...同时,环链表在很多实际问题中都有应用,掌握其相关知识对提升编程能力至关重要。通过分析和学习"hasCycle-master"中的代码,可以进一步提升对环链表的理解和应用技巧。

    12种常用数据结构 无向图 有向图 (邻接链表实现) 链表 环链表 最小堆 栈 最小生成树 栈 UFSets集合

    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

    Linux运维-嵌入式物联网开发教程-有头双向环链空链表创建.mp4

    约瑟夫(Josephus)环问题

    2、 约瑟夫(Josephus)环问题:编号为1,2,3,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止。报m...

    关于有环链表的问题

    在一个有环链表中,至少存在一个节点的指针不是指向链表中的下一个节点而是指向链表中的某个先前节点,从而形成了一个闭合的环路。 #### 二、判断链表中是否存在环 判断一个链表中是否存在环可以通过“快慢指针”的...

    链表问题11——两个单链表相交的系列问题(三):判断两个有环链表是否相交

    判断两个有环链表是否相交,相交则返回第一个相交节点,否则返回null 在考虑此问题时,根据前面几篇文章的解法,我们已经得到了各自链表的入环节点,分别为loop1和loop2 思路 以下是问题三的具体解决过程: 如果loop...

    判断单链表中是否存在环

    如果快指针到达了链表尾部,则表示链表为无环链表。 ### 实现代码分析 在给定的部分内容中,我们可以看到具体的C语言实现代码。这段代码实现了链表的创建、添加环以及检测环的功能。 - **链表创建**:`create`...

    STAHL环链葫芦

    - **有安全意识的操作**:强调操作人员在使用设备时必须保持警觉,时刻注意可能的风险。 - **组织的安全防范措施**:企业应建立一套安全操作流程,确保所有人员都遵守安全规定。 - **电气设备的注意事项**:由于环链...

    约瑟夫环链式结构

    自己编写得约瑟夫环,有需要得做数据结构得可以下载来看看

    Linux运维-嵌入式物联网开发教程-有头双向环链查找和删除前备份.mp4

    Linux运维-嵌入式物联网开发教程-一维数组传参.mp4

    链表相关问题的完整代码

    链表相关问题的完整代码,包括测试类和关键代码: **0、将链表翻转** **1、判断链表是否有环** **2、寻找环的入口点** **3、计算环的节点数** ...**6、判断两个无环链表是否相交** **7、寻找两个链表的相交的节点**

    矿用圆环链.pdf

    随着煤炭需求的增长,刮板输送机的技术进步推动了矿用圆环链的发展。 矿用高强度圆环链的发展主要体现在以下几个方面: 1. **钢材的进步**:早期的矿用圆环链采用碳锰钢,含碳量低,合金元素少,淬透性较低,适用...

Global site tag (gtag.js) - Google Analytics