鏈表是常用的幾種數(shù)據(jù)結(jié)構(gòu)其中一個(gè)。鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間,實(shí)現(xiàn)靈動(dòng)的內(nèi)存動(dòng)態(tài)管理。本篇文章將通過 Java 代碼展示為大家介紹如何判斷一個(gè)鏈表是個(gè)有環(huán)鏈表,以及有環(huán)鏈表的入口點(diǎn)。
鏈表是常用的幾種數(shù)據(jù)結(jié)構(gòu)其中一個(gè)。鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間,實(shí)現(xiàn)靈動(dòng)的內(nèi)存動(dòng)態(tài)管理。本篇文章將通過 Java 代碼展示為大家介紹如何判斷一個(gè)鏈表是個(gè)有環(huán)鏈表,以及有環(huán)鏈表的入口點(diǎn)。
1.首先定義一個(gè)單鏈表;
var ,next,是單鏈表中的屬性,分別表示節(jié)點(diǎn)值和下一個(gè)節(jié)點(diǎn)的指向;
代碼如下:
//定義一個(gè)鏈表
class List{
public int var;
public List next;
//有參構(gòu)造
public List(int var) {
this.var = var;
}
//無參構(gòu)造
public List() {
}
//創(chuàng)建一個(gè)帶環(huán)的鏈表
public List Create(){
List a = new List(1);
List b = new List(2);
List c = new List(3);
List d = new List(4);
List e = new List(5);
List f = new List(6);
a.next = b;
b.next =c;
c.next = d;
d.next =e;
e.next = f;
f.next =d;
return a;
}
2.編寫判斷是否存在環(huán)
如果存在,則返回這個(gè)節(jié)點(diǎn),如果不存在則返回null,定義快慢指針,如果快的追上了慢的指針,那么這個(gè)鏈表必存在環(huán),如果沒有追上,或者都為null,那么這個(gè)鏈表沒有環(huán);
代碼如下:
//判斷是否有環(huán),并找到相遇的節(jié)點(diǎn)
public List MeetingNode(List node){
List slow = new List();
List fast = new List();
if(node==null) return null;
slow = node.next;
if(slow==null) return null;
fast=slow.next;
while (fast!=null && slow!=null){
if (fast==slow){
return fast; //fast追上了slow,確定是一個(gè)有環(huán)的鏈表;
}
slow = slow.next;
fast = fast.next;
if(fast!=null){
fast = fast.next;
}
}
return null;
}
3.尋找入口節(jié)點(diǎn)
先讓快指針先走環(huán)的節(jié)點(diǎn)的個(gè)數(shù)步,在讓慢指針開始走,如果兩個(gè)指針相遇的話,那么相遇的節(jié)點(diǎn)必然是環(huán)的入口節(jié)點(diǎn)
代碼如下:
public List Enterdear(List node){
if(node==null) return null;
if(MeetingNode(node)==null) return null;
int count =1;
List res2;
List res1 = MeetingNode(node);
while (res1.next!=MeetingNode(node)){
res1 = res1.next;
count++;
}
res1 = node;
for(int i = 0;i<count;i++){
res1 =res1.next;
}
res2 = node;
while (res1!=res2 && res1!=null && res2!=null){
res1 = res1.next;
res2 = res2.next;
}
return res1;
}
}
main函數(shù)測(cè)試;
public class Deom {
public static void main(String[] args) {
List SB = new List();
List res = SB.Create();
List dear= SB.Enterdear(res);
System.out.println(dear.var);
}
}
以上就是用 Java 判斷一個(gè)鏈表是否有環(huán)和確定它的入口節(jié)點(diǎn)是什么的詳細(xì)內(nèi)容,想要了解更多 java 數(shù)據(jù)結(jié)構(gòu)的相關(guān)資料請(qǐng)關(guān)注W3Cschool其它相關(guān)文章!