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://myzitong.com/article/hsoojo.html