編寫兩個java類，一個為Linkitem.java，另一個為測試類LinklistTest.java，分別如下：
古藺網(wǎng)站建設公司創(chuàng)新互聯(lián),古藺網(wǎng)站設計制作，有大型網(wǎng)站制作公司豐富經(jīng)驗。已為古藺成百上千家提供企業(yè)網(wǎng)站建設服務。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站制作要多少錢，請找那個售后服務好的古藺做網(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) {
//初始化鏈表項
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();
//添加個鏈表項
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)鏈表。");
}
}
}
*****************************************************
運行結果為：
此鏈表為循環(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指向一個新的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.判斷有沒有環(huán)
Node list1 = top;//都至于起點即根節(jié)點 慢
Node list2 = top; //快
//思想：兩個數(shù)同時跑，如果相遇，即是有環(huán)
boolean flag=false;
for(;(!(list1==list2))||(list1==list2list1==top);){
System.out.println("進入循環(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("此鏈表沒有環(huán)");
}else if(flag==false){
System.out.println("此鏈表有環(huán)");
}
//2.環(huán)的大小是多少？讓他倆在相遇點一起跑，再次相遇慢的跑的舉例即是環(huán)的長度
int count=0;
for(;;){
list1=list1.next;
list2=list2.next.next;
count++;
if(list1==list2){
break;
}
}
System.out.println("環(huán)的長度是：" + count);
//3環(huán)的切入點是多少？
list1=top;
for(;!(list1==list2);){
list1=list1.next;
list2=list2.next;
}
System.out.println("環(huán)的切入點是"+list1.n);
//4.鏈表的長度：
list1=top;
for(;!(list1==list2);){
list1=list1.next;//將一個拉回節(jié)點
count++;
}
System.out.println("鏈表的長度為：" + count);
}
}
//鏈表的節(jié)點：
class Node{
int n;
Node next;
}
方法一：首先從頭節(jié)點開始，依次遍歷單鏈表的每一個節(jié)點。每遍歷到一個新節(jié)點，就從頭節(jié)點重新遍歷新節(jié)點之前的所有節(jié)點，用新節(jié)點ID和此節(jié)點之前所有節(jié)點ID依次作比較。如果發(fā)現(xiàn)新節(jié)點之前的所有節(jié)點當中存在相同節(jié)點ID，則說明該節(jié)點被遍歷過兩次，鏈表有環(huán)；如果之前的所有節(jié)點當中不存在相同的節(jié)點，就繼續(xù)遍歷下一個新節(jié)點，繼續(xù)重復剛才的操作。
例如這樣的鏈表：A-B-C-D-B-C-D，
當遍歷到節(jié)點D的時候，我們需要比較的是之前的節(jié)點A、B、C，不存在相同節(jié)點。這時候要遍歷的下一個新節(jié)點是B，B之前的節(jié)點A、B、C、D中恰好也存在B，因此B出現(xiàn)了兩次，判斷出鏈表有環(huán)。
假設從鏈表頭節(jié)點到入環(huán)點的距離是D，鏈表的環(huán)長是S。D+S是鏈表總節(jié)點數(shù)。那么算法的時間復雜度是0+1+2+3+….+(D+S-1)
=
(D+S-1)*(D+S)/2
，
可以簡單地理解成
O(N*N)。而此算法沒有創(chuàng)建額外存儲空間，空間復雜度可以簡單地理解成為O(1)。
方法二：首先創(chuàng)建一個以節(jié)點ID為鍵的HashSet集合，用來存儲曾經(jīng)遍歷過的節(jié)點。然后同樣是從頭節(jié)點開始，依次遍歷單鏈表的每一個節(jié)點。每遍歷到一個新節(jié)點，就用新節(jié)點和HashSet集合當中存儲的節(jié)點作比較，如果發(fā)現(xiàn)HashSet當中存在相同節(jié)點ID，則說明鏈表有環(huán)，如果HashSet當中不存在相同的節(jié)點ID，就把這個新節(jié)點ID存入HashSet，之后進入下一節(jié)點，繼續(xù)重復剛才的操作。
這個方法在流程上和方法一類似，本質的區(qū)別是使用了HashSet作為額外的緩存。
假設從鏈表頭節(jié)點到入環(huán)點的距離是D，鏈表的環(huán)長是S。而每一次HashSet查找元素的時間復雜度是O(1),
所以總體的時間復雜度是1*(D+S)=D+S，可以簡單理解為O(N)。而算法的空間復雜度還是D+S-1，可以簡單地理解成O(N)。
方法三：首先創(chuàng)建兩個指針1和2（在Java里就是兩個對象引用），同時指向這個鏈表的頭節(jié)點。然后開始一個大循環(huán)，在循環(huán)體中，讓指針1每次向下移動一個節(jié)點，讓指針2每次向下移動兩個節(jié)點，然后比較兩個指針指向的節(jié)點是否相同。如果相同，則判斷出鏈表有環(huán)，如果不同，則繼續(xù)下一次循環(huán)。
例如鏈表A-B-C-D-B-C-D，兩個指針最初都指向節(jié)點A，進入第一輪循環(huán)，指針1移動到了節(jié)點B，指針2移動到了C。第二輪循環(huán)，指針1移動到了節(jié)點C，指針2移動到了節(jié)點B。第三輪循環(huán)，指針1移動到了節(jié)點D，指針2移動到了節(jié)點D，此時兩指針指向同一節(jié)點，判斷出鏈表有環(huán)。
此方法也可以用一個更生動的例子來形容：在一個環(huán)形跑道上，兩個運動員在同一地點起跑，一個運動員速度快，一個運動員速度慢。當兩人跑了一段時間，速度快的運動員必然會從速度慢的運動員身后再次追上并超過，原因很簡單，因為跑道是環(huán)形的。
你的remove方法不對，你的方法每次刪掉的是從head開始第m個位置的節(jié)點，
但約瑟夫環(huán)需要的是要刪掉每次循環(huán)數(shù)到m的位置的節(jié)點。
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++;
}
}
}
重慶分公司
重慶分公司
