急急急 如何用Java語(yǔ)言實(shí)現(xiàn)判斷一個(gè)鏈表是否存在循環(huán)連接的算法

編寫兩個(gè)java類，一個(gè)為L(zhǎng)inkitem.java，另一個(gè)為測(cè)試類LinklistTest.java，分別如下：

古藺網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián),古藺網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為古藺成百上千家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站制作要多少錢，請(qǐng)找那個(gè)售后服務(wù)好的古藺做網(wǎng)站的公司定做！

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

//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) {

//初始化鏈表項(xiàng)

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);

//新建存放鏈表的數(shù)組列表

ArrayListLinkitem list = new ArrayListLinkitem();

//添加個(gè)鏈表項(xiàng)

list.add(a);

list.add(b);

list.add(c);

list.add(d);

//是否為循環(huán)鏈表的判斷變量

boolean link = false;

Linkitem start = a;

Linkitem current = a;

//判斷循環(huán)鏈表

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("此鏈表為循環(huán)鏈表。");

} else {

System.out.println("此鏈表不是循環(huán)鏈表。");

}

}

}

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

運(yùn)行結(jié)果為：

此鏈表為循環(huán)鏈表。

用Java實(shí)現(xiàn)判斷鏈表是否有環(huán)，環(huán)的大小，環(huán)的

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指向一個(gè)新的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回到起點(diǎn)，指向頭結(jié)點(diǎn)

//1.判斷有沒(méi)有環(huán)

Node list1 = top;//都至于起點(diǎn)即根節(jié)點(diǎn) 慢

Node list2 = top; //快

//思想：兩個(gè)數(shù)同時(shí)跑，如果相遇，即是有環(huán)

boolean flag=false;

for(;(!(list1==list2))||(list1==list2list1==top);){

System.out.println("進(jìn)入循環(huán)了");

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("此鏈表沒(méi)有環(huán)");

}else if(flag==false){

System.out.println("此鏈表有環(huán)");

}

//2.環(huán)的大小是多少？讓他倆在相遇點(diǎn)一起跑，再次相遇慢的跑的舉例即是環(huán)的長(zhǎng)度

int count=0;

for(;;){

list1=list1.next;

list2=list2.next.next;

count++;

if(list1==list2){

break;

}

}

System.out.println("環(huán)的長(zhǎng)度是：" + count);

//3環(huán)的切入點(diǎn)是多少？

list1=top;

for(;!(list1==list2);){

list1=list1.next;

list2=list2.next;

}

System.out.println("環(huán)的切入點(diǎn)是"+list1.n);

//4.鏈表的長(zhǎng)度：

list1=top;

for(;!(list1==list2);){

list1=list1.next;//將一個(gè)拉回節(jié)點(diǎn)

count++;

}

System.out.println("鏈表的長(zhǎng)度為：" + count);

}

}

//鏈表的節(jié)點(diǎn)：

class Node{

int n;

Node next;

}

Java判斷單鏈表是否有環(huán)的兩種實(shí)現(xiàn)方法

方法一：首先從頭節(jié)點(diǎn)開(kāi)始，依次遍歷單鏈表的每一個(gè)節(jié)點(diǎn)。每遍歷到一個(gè)新節(jié)點(diǎn)，就從頭節(jié)點(diǎn)重新遍歷新節(jié)點(diǎn)之前的所有節(jié)點(diǎn)，用新節(jié)點(diǎn)ID和此節(jié)點(diǎn)之前所有節(jié)點(diǎn)ID依次作比較。如果發(fā)現(xiàn)新節(jié)點(diǎn)之前的所有節(jié)點(diǎn)當(dāng)中存在相同節(jié)點(diǎn)ID，則說(shuō)明該節(jié)點(diǎn)被遍歷過(guò)兩次，鏈表有環(huán)；如果之前的所有節(jié)點(diǎn)當(dāng)中不存在相同的節(jié)點(diǎn)，就繼續(xù)遍歷下一個(gè)新節(jié)點(diǎn)，繼續(xù)重復(fù)剛才的操作。

例如這樣的鏈表：A-B-C-D-B-C-D，

當(dāng)遍歷到節(jié)點(diǎn)D的時(shí)候，我們需要比較的是之前的節(jié)點(diǎn)A、B、C，不存在相同節(jié)點(diǎn)。這時(shí)候要遍歷的下一個(gè)新節(jié)點(diǎn)是B，B之前的節(jié)點(diǎn)A、B、C、D中恰好也存在B，因此B出現(xiàn)了兩次，判斷出鏈表有環(huán)。

假設(shè)從鏈表頭節(jié)點(diǎn)到入環(huán)點(diǎn)的距離是D，鏈表的環(huán)長(zhǎng)是S。D+S是鏈表總節(jié)點(diǎn)數(shù)。那么算法的時(shí)間復(fù)雜度是0+1+2+3+….+(D+S-1)

=

(D+S-1)*(D+S)/2

，

可以簡(jiǎn)單地理解成

O(N*N)。而此算法沒(méi)有創(chuàng)建額外存儲(chǔ)空間，空間復(fù)雜度可以簡(jiǎn)單地理解成為O(1)。

方法二：首先創(chuàng)建一個(gè)以節(jié)點(diǎn)ID為鍵的HashSet集合，用來(lái)存儲(chǔ)曾經(jīng)遍歷過(guò)的節(jié)點(diǎn)。然后同樣是從頭節(jié)點(diǎn)開(kāi)始，依次遍歷單鏈表的每一個(gè)節(jié)點(diǎn)。每遍歷到一個(gè)新節(jié)點(diǎn)，就用新節(jié)點(diǎn)和HashSet集合當(dāng)中存儲(chǔ)的節(jié)點(diǎn)作比較，如果發(fā)現(xiàn)HashSet當(dāng)中存在相同節(jié)點(diǎn)ID，則說(shuō)明鏈表有環(huán)，如果HashSet當(dāng)中不存在相同的節(jié)點(diǎn)ID，就把這個(gè)新節(jié)點(diǎn)ID存入HashSet，之后進(jìn)入下一節(jié)點(diǎn)，繼續(xù)重復(fù)剛才的操作。

這個(gè)方法在流程上和方法一類似，本質(zhì)的區(qū)別是使用了HashSet作為額外的緩存。

假設(shè)從鏈表頭節(jié)點(diǎn)到入環(huán)點(diǎn)的距離是D，鏈表的環(huán)長(zhǎng)是S。而每一次HashSet查找元素的時(shí)間復(fù)雜度是O(1),

所以總體的時(shí)間復(fù)雜度是1*(D+S)=D+S，可以簡(jiǎn)單理解為O(N)。而算法的空間復(fù)雜度還是D+S-1，可以簡(jiǎn)單地理解成O(N)。

方法三：首先創(chuàng)建兩個(gè)指針1和2（在Java里就是兩個(gè)對(duì)象引用），同時(shí)指向這個(gè)鏈表的頭節(jié)點(diǎn)。然后開(kāi)始一個(gè)大循環(huán)，在循環(huán)體中，讓指針1每次向下移動(dòng)一個(gè)節(jié)點(diǎn)，讓指針2每次向下移動(dòng)兩個(gè)節(jié)點(diǎn)，然后比較兩個(gè)指針指向的節(jié)點(diǎn)是否相同。如果相同，則判斷出鏈表有環(huán)，如果不同，則繼續(xù)下一次循環(huán)。

例如鏈表A-B-C-D-B-C-D，兩個(gè)指針最初都指向節(jié)點(diǎn)A，進(jìn)入第一輪循環(huán)，指針1移動(dòng)到了節(jié)點(diǎn)B，指針2移動(dòng)到了C。第二輪循環(huán)，指針1移動(dòng)到了節(jié)點(diǎn)C，指針2移動(dòng)到了節(jié)點(diǎn)B。第三輪循環(huán)，指針1移動(dòng)到了節(jié)點(diǎn)D，指針2移動(dòng)到了節(jié)點(diǎn)D，此時(shí)兩指針指向同一節(jié)點(diǎn)，判斷出鏈表有環(huán)。

此方法也可以用一個(gè)更生動(dòng)的例子來(lái)形容：在一個(gè)環(huán)形跑道上，兩個(gè)運(yùn)動(dòng)員在同一地點(diǎn)起跑，一個(gè)運(yùn)動(dòng)員速度快，一個(gè)運(yùn)動(dòng)員速度慢。當(dāng)兩人跑了一段時(shí)間，速度快的運(yùn)動(dòng)員必然會(huì)從速度慢的運(yùn)動(dòng)員身后再次追上并超過(guò)，原因很簡(jiǎn)單，因?yàn)榕艿朗黔h(huán)形的。

java循環(huán)單鏈表實(shí)現(xiàn)約瑟夫環(huán)，我的代碼出列順序不正確

你的remove方法不對(duì)，你的方法每次刪掉的是從head開(kāi)始第m個(gè)位置的節(jié)點(diǎn)，

但約瑟夫環(huán)需要的是要?jiǎng)h掉每次循環(huán)數(shù)到m的位置的節(jié)點(diǎn)。

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

}

}

}

分享標(biāo)題：java鏈表有環(huán)測(cè)試代碼,環(huán)形鏈表java
文章鏈接：http://jinyejixie.com/article20/hsoojo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供虛擬主機(jī)、ChatGPT、面包屑導(dǎo)航、網(wǎng)站收錄、網(wǎng)站營(yíng)銷、微信小程序

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)