java链表有环测试代码,环形链表java
急急急 如何用Java语言实现判断一个链表是否存在循环连接的算法
编写两个java类，一个为Linkitem.java，另一个为测试类LinklistTest.java，分别如下：
古蔺网站建设公司创新互联,古蔺网站设计制作，有大型网站制作公司丰富经验。已为古蔺成百上千家提供企业网站建设服务。企业网站搭建\成都外贸网站制作要多少钱，请找那个售后服务好的古蔺做网站的公司定做！
*****************************************************
//Linkitem.java
public class Linkitem {
Linkitem previous;
String data;
Linkitem next;
public Linkitem() {
}
public Linkitem(Linkitem previous, String data, Linkitem next) {
super();
this.previous = previous;
this.data = data;
this.next = next;
}
public Linkitem getPrevious() {
return previous;
}
public void setPrevious(Linkitem previous) {
this.previous = previous;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public Linkitem getNext() {
return next;
}
public void setNext(Linkitem next) {
this.next = next;
}
}
*****************************************************
//LinklistTest.java
import java.util.ArrayList;
public class LinklistTest {
public static void main(String[] args) {
//初始化链表项
Linkitem a = new Linkitem(null, "a", null);
Linkitem b = new Linkitem(null, "b", null);
Linkitem c = new Linkitem(null, "c", null);
Linkitem d = new Linkitem(null, "d", null);
a.setPrevious(d);
a.setNext(b);
b.setPrevious(a);
b.setNext(c);
c.setPrevious(b);
c.setNext(d);
d.setPrevious(c);
d.setNext(a);
//新建存放链表的数组列表
ArrayListLinkitem list = new ArrayListLinkitem();
//添加个链表项
list.add(a);
list.add(b);
list.add(c);
list.add(d);
//是否为循环链表的判断变量
boolean link = false;
Linkitem start = a;
Linkitem current = a;
//判断循环链表
for (int i = 0; i list.size(); i++) {
current = current.next;
if (start.data.equals(current.data)) {
link = true;
}
}
//输出
if (link == true) {
System.out.println("此链表为循环链表。");
} else {
System.out.println("此链表不是循环链表。");
}
}
}
*****************************************************
运行结果为：
此链表为循环链表。
用Java实现判断链表是否有环，环的大小，环的
public static void main(String[] args) {
Node list = new Node();
Node top = list;
list.n=1;
for(int i = 2;i 10; i++){
//list的next指向一个新的Node
list.next = new Node();
//新的Node的n赋值为i
list.next.n=i;
//list指向新的Node
list = list.next;
}
list.next = top.next.next.next;
list=top; //让list回到起点，指向头结点
//1.判断有没有环
Node list1 = top;//都至于起点即根节点 慢
Node list2 = top; //快
//思想：两个数同时跑，如果相遇，即是有环
boolean flag=false;
for(;(!(list1==list2))||(list1==list2list1==top);){
System.out.println("进入循环了");
if(list1==null||list1.next==null){
flag=true;
break;
}
list1=list1.next;
list2=list2.next.next;
System.out.println(list1.n + ":" + list2.n);
}
if(flag==true){
System.out.println("此链表没有环");
}else if(flag==false){
System.out.println("此链表有环");
}
//2.环的大小是多少？让他俩在相遇点一起跑，再次相遇慢的跑的举例即是环的长度
int count=0;
for(;;){
list1=list1.next;
list2=list2.next.next;
count++;
if(list1==list2){
break;
}
}
System.out.println("环的长度是：" + count);
//3环的切入点是多少？
list1=top;
for(;!(list1==list2);){
list1=list1.next;
list2=list2.next;
}
System.out.println("环的切入点是"+list1.n);
//4.链表的长度：
list1=top;
for(;!(list1==list2);){
list1=list1.next;//将一个拉回节点
count++;
}
System.out.println("链表的长度为：" + count);
}
}
//链表的节点：
class Node{
int n;
Node next;
}
Java判断单链表是否有环的两种实现方法
方法一：首先从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就从头节点重新遍历新节点之前的所有节点，用新节点ID和此节点之前所有节点ID依次作比较。如果发现新节点之前的所有节点当中存在相同节点ID，则说明该节点被遍历过两次，链表有环；如果之前的所有节点当中不存在相同的节点，就继续遍历下一个新节点，继续重复刚才的操作。
例如这样的链表：A-B-C-D-B-C-D，
当遍历到节点D的时候，我们需要比较的是之前的节点A、B、C，不存在相同节点。这时候要遍历的下一个新节点是B，B之前的节点A、B、C、D中恰好也存在B，因此B出现了两次，判断出链表有环。
假设从链表头节点到入环点的距离是D，链表的环长是S。D+S是链表总节点数。那么算法的时间复杂度是0+1+2+3+….+(D+S-1)
=
(D+S-1)*(D+S)/2
，
可以简单地理解成
O(N*N)。而此算法没有创建额外存储空间，空间复杂度可以简单地理解成为O(1)。
方法二：首先创建一个以节点ID为键的HashSet集合，用来存储曾经遍历过的节点。然后同样是从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就用新节点和HashSet集合当中存储的节点作比较，如果发现HashSet当中存在相同节点ID，则说明链表有环，如果HashSet当中不存在相同的节点ID，就把这个新节点ID存入HashSet，之后进入下一节点，继续重复刚才的操作。
这个方法在流程上和方法一类似，本质的区别是使用了HashSet作为额外的缓存。
假设从链表头节点到入环点的距离是D，链表的环长是S。而每一次HashSet查找元素的时间复杂度是O(1),
所以总体的时间复杂度是1*(D+S)=D+S，可以简单理解为O(N)。而算法的空间复杂度还是D+S-1，可以简单地理解成O(N)。
方法三：首先创建两个指针1和2（在Java里就是两个对象引用），同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针1每次向下移动一个节点，让指针2每次向下移动两个节点，然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环。
例如链表A-B-C-D-B-C-D，两个指针最初都指向节点A，进入第一轮循环，指针1移动到了节点B，指针2移动到了C。第二轮循环，指针1移动到了节点C，指针2移动到了节点B。第三轮循环，指针1移动到了节点D，指针2移动到了节点D，此时两指针指向同一节点，判断出链表有环。
此方法也可以用一个更生动的例子来形容：在一个环形跑道上，两个运动员在同一地点起跑，一个运动员速度快，一个运动员速度慢。当两人跑了一段时间，速度快的运动员必然会从速度慢的运动员身后再次追上并超过，原因很简单，因为跑道是环形的。
java循环单链表实现约瑟夫环，我的代码出列顺序不正确
你的remove方法不对，你的方法每次删掉的是从head开始第m个位置的节点，
但约瑟夫环需要的是要删掉每次循环数到m的位置的节点。
remove方法可以去掉，再把out方法改一下就可以了。
public void out(int m) throws Exception {
Node p = head;
Node pre = null;
int count = 1;
while (curlen 0) {
if (count == m) {
System.out.print(p.getData() + " ");
if(pre != null){
pre.setNext(p.getNext());
}
p = p.getNext();
curlen = curlen - 1;
count = 1;
} else {
pre = p;
p = p.getNext();
count++;
}
}
}
网站名称：java链表有环测试代码,环形链表java
本文地址：http://6mz.cn/article/hsoojo.html