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("此链表不是循环链表。");

}

}

}

*****************************************************

运行结果为：

此链表为循环链表。

相关问答

Q1: 用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;

}

Q2: 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，此时两指针指向同一节点，判断出链表有环。

此方法也可以用一个更生动的例子来形容：在一个环形跑道上，两个运动员在同一地点起跑，一个运动员速度快，一个运动员速度慢。当两人跑了一段时间，速度快的运动员必然会从速度慢的运动员身后再次追上并超过，原因很简单，因为跑道是环形的。

Q3: 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++;

}

}

}