java实现单链表中是否有环的方法详解
这是一道微软经典笔试题，就是两个指针h1,h2都从头开始遍历单链表，h1每次向前走1步，h2每次向前走2步，如果h2碰到了NULL，说明环不存在；如果h2碰到本应在身后的h1说明环存在（也就是发生了套圈）。
如果环不存在，一定是h2先碰到NULL：
如果环存在，h2与h1一定会相遇，而且相遇的点在环内：h2比h1遍历的速度快，一定不会在开始的那段非环的链表部分相遇，所以当h1,h2都进入环后，h2每次移动都会使h2与h1之间在前进方向上的差距缩小1，最后，会使得h1和h2差距减少为0，也即相遇
package org.myorg;
public class Test{
public static boolean isExsitLoop(SingleList a) {
Node<T> slow = a.head;
Node<T> fast = a.head; while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast)
return true;
}
return false;
}
public static void main(String args[]){
SingleList list = new SingleList();
for(int i=0;i<100;i++){
list.add(i);
}
System.out.print(SingleList.isExistingLoop(list));
}
}
package org.myorg;
public class Node{
public Object data; //节点存储的数据对象
public Node next; //指向下一个节点的引用
public Node(Object value){
this.data = value;
}
public Node(){
this.data = null;
this.next = null;
}
}
package org.myorg;
public class SingleList{
private int size;
private Node head;
private void init(){
this.size = 0;
this.head = new Node();
}
public SingleList(){
init();
}
public boolean contains(Object value){
boolean flag = false;
Node p = head.next;
while(p!=null){
if(value.equals(p.data)){
flag = true;
break;
}else(
p = p.next;
)
}
return flag;
}
public boolean add(Object value){
if(contains(value))
return false;
else{
Node p = new Node(value);
p.next=head.next;
head.next = p;
size++;
}
return true;
}
}
相关推荐
-
java实现单链表之逆序
下面一段代码准确的介绍了java实现单链表逆序,具体内容就不做详解了,有需要的朋友可以直接拷贝了 package com.ckw.mianshi; /** * java 实现单链表的逆序 * @author Administrator * */ public class SingleLinkedReverse { class Node{ int data; Node next; public Node(int data){ this.data = data; } } public static
-
Java硬币翻转倍数递增试算实例
//有何不足或者问题希望能够得到各位的多多指正,不胜感激 复制代码 代码如下: import java.util.Scanner; /** * * @author cc 举例 100枚硬币,最初全部朝下,第一次将所有硬币反转过来, 第二次反转位置是2的倍数的硬币, * 第三次反转3的倍数,.....执行一百次,问最终共有多少个硬币面朝上? * * 1.硬币正反使用数组 1.0表示,1表示正面,0表示反面: * * *
-
java实现数据结构单链表示例(java单链表)
复制代码 代码如下: /** * 单向链表 * */public class NodeList<E> { private static class Node<E> { // 节点类 E data; // 节点上的数据 Node<E> next; // 指向下一个节点 Node(E e) { this.data = e; this.next = null; } } private Node<E> head; // 链表的头节点 private N
-
Java实现单链表翻转实例代码
Java实现单链表反转,递归和非递归两种形式 /** * 反转单链表 */ /** * 定义链表 * * @author 16026 * */ class Node { int val; Node next; public Node(int val) { this.val = val; } } public class ReverseList { /** * 反转链表 * * @param head * @return */ public static Node reverseList(Node
-
javafx实现图片3D翻转效果方法实例
实现步骤: 1.定义FlipView对象.包含以下属性: 复制代码 代码如下: //正面视图 public Node frontNode; //反面视图 public Node backNode; //是否翻转 boolean flipped = false; //翻转角度 DoubleProperty time = new SimpleDoubleProperty(Math.PI / 2); //正面翻转特效 PerspectiveTransform frontEffect = new Per
-
Java单链表基本操作的实现
最近被问到链表,是一个朋友和我讨论Java的时候说的.说实话,我学习编程的近一年时间里,学到的东西还是挺少的.语言是学了Java和C#,关于Web的学了一点Html+css+javascript.因为比较偏好,学习WinForm时比较认真,数据库操作也自己有所研究.但链表这个东西我还真没有学习和研究过,加上最近自己在看WPF,而课程也到了JSP了,比较紧. 但是我还是抽了一个晚上加半天的时间看了一下单向链表.并且使用Java试着写了一个实例出来.没有接触过链表的朋友可以作为参考,希望大家多提宝贵
-
Java 其中翻转字符串的实现方法
给大家介绍其中常用和不常用的将字符串翻转过来的方法: 复制代码 代码如下: import java.util.Stack; public class StringReverse { public static String reverse1(String s) { int length = s.length(); if (length <= 1) return s; String left = s.substring(0, length / 2); String right = s.substr
-
java实现单链表中是否有环的方法详解
这是一道微软经典笔试题,就是两个指针h1,h2都从头开始遍历单链表,h1每次向前走1步,h2每次向前走2步,如果h2碰到了NULL,说明环不存在:如果h2碰到本应在身后的h1说明环存在(也就是发生了套圈). 如果环不存在,一定是h2先碰到NULL: 如果环存在,h2与h1一定会相遇,而且相遇的点在环内:h2比h1遍历的速度快,一定不会在开始的那段非环的链表部分相遇,所以当h1,h2都进入环后,h2每次移动都会使h2与h1之间在前进方向上的差距缩小1,最后,会使得h1和h2差距减少为0,也即相遇
-
java实现单链表增删改查的实例代码详解
package 数据结构算法.链表; /* *定义节点 * 链表由节点构成 */ public class Node<E> { private E e; //数据data private Node<E> next; //指向下一个节点 public Node() { } public Node(E e) { this.e = e; } public Node<E> getNext() { return next; } public void setNext(Node&l
-
Java链表中元素删除的实现方法详解【只删除一个元素情况】
本文实例讲述了Java链表中元素删除的实现方法.分享给大家供大家参考,具体如下: 该部分与上一节是息息相关的,关于如何在链表中删除元素,我们一步一步来分析: 一.图示删除逻辑 假设我们需要在链表中删除索引为2位置的元素,此时链表结构为: 若要删除索引为2位置的元素,需要获取索引为2位置的元素之前的前置节点(此时为索引为1的位置的元素),因此我们需要设计一个变量prev来记录前置节点. 1.初始时变量prev指向虚拟头结点dummyHead: 2.寻找到前置节点位置,(对于该例子前置节点为索引为1
-
java实现单链表中的增删改
本文实例为大家分享了java实现单链表中增删改的具体代码,供大家参考,具体内容如下 什么是链表 链表是有序的列表,但是它在内存中是存储如下 小结: 链表是以节点的方式来存储,是链式存储 每个节点包含data 域, next 域:指向下一个节点. 如图:发现链表的各个节点不一定是连续存储. 链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定 单链表(带头结点) 逻辑结构示意图如下 单链表的增删改应用实例 使用带head 头的单向链表实现——三国英雄排行榜管理完成对英雄人物的增删改查操作
-
Java多线程高并发中的Fork/Join框架机制详解
1.Fork/Join框架简介 Fork/Join 它可以将一个大的任务拆分成多个子任务进行并行处理,最后将子任务结果合并成最后的计算结果,并进行输出.Fork/Join 框架要完成两件事情: Fork:把一个复杂任务进行分拆,大事化小 :把一个复杂任务进行分拆,大事化小 Join:把分拆任务的结果进行合并 在 Java 的 Fork/Join 框架中,使用两个类完成上述操作: ForkJoinTask: 我们要使用 Fork/Join 框架,首先需要创建一个 ForkJoin 任务.该类提供了
-
Java中Optional类及orElse方法详解
目录 引言 Java 中的 Optional 类 ofNullable() 方法 orElse() 方法 案例 orElseGet() 方法 案例 orElse() 与 orElseGet() 之间的区别 引言 为了让我更快的熟悉代码,前段时间组长交代了一个小任务,大致就是让我整理一下某个模块中涉及的 sql,也是方便我有目的的看代码,也是以后方便他们查问题(因为这个模块,涉及的判断很多,所以之前如果 sql 出错了,查问题比较繁琐). 昨天算是基本完成了,然后今天组长就让给我看一个该模块的缺陷
-
使用Java构造和解析Json数据的两种方法(详解二)
JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式,采用完全独立于语言的文本格式,是理想的数据交换格式.同时,JSON是 JavaScript 原生格式,这意味着在 JavaScript 中处理 JSON数据不须要任何特殊的 API 或工具包. 在www.json.org上公布了很多JAVA下的json构造和解析工具,其中org.json和json-lib比较简单,两者使用上差不多但还是有些区别.下面接着介绍用org.json构造和解析Json数据的方法
-
使用Java构造和解析Json数据的两种方法(详解一)
JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式,采用完全独立于语言的文本格式,是理想的数据交换格式.同时,JSON是 JavaScript 原生格式,这意味着在 JavaScript 中处理 JSON数据不须要任何特殊的 API 或工具包. 在www.json.org上公布了很多JAVA下的json构造和解析工具,其中org.json和json-lib比较简单,两者使用上差不多但还是有些区别.下面首先介绍用json-lib构造和解析Json数据的方法
-
Struts中使用validate()输入校验方法详解
1.在ActionSupport中有一个validate()方法,这个方法是验证方法,它会在execute()方法执行之前执行,所以能够起到很好的验证的作用. @Override //重写Action中的validate()方法 public void validate() { if(null==this.username||this.username.length()<4||this.username.length()>6){ this.addActionError("userna
-
struts2中使用注解配置Action方法详解
使用注解来配置Action可以实现零配置,零配置将从基于纯XML的配置转化为基于注解的配置.使用注解,可以在大多数情况下避免使用struts.xml文件来进行配置. struts2框架提供了四个与Action相关的注解类型,分别为ParentPackage.Namespace.Result和Action. ParentPackage:ParentPackage注解用于指定Action所在的包要继承的父包.该注解只有一个value参数.用于指定要继承的父包. 示例: 使用ParentPackage