java如何確定一個鏈表有環(huán)及入口節(jié)點
如何確定一個鏈表有環(huán),入口節(jié)點是什么?
1.首先定義一個單鏈表;
var ,next,是單鏈表中的屬性,分別表示節(jié)點值和下一個節(jié)點的指向;
代碼如下:
//定義一個鏈表 class List{ public int var; public List next; //有參構(gòu)造 public List(int var) { this.var = var; } //無參構(gòu)造 public List() { } //創(chuàng)建一個帶環(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)
如果存在,則返回這個節(jié)點,如果不存在則返回null,定義快慢指針,如果快的追上了慢的指針,那么這個鏈表必存在環(huán),如果沒有追上,或者都為null,那么這個鏈表沒有環(huán);
代碼如下:
//判斷是否有環(huán),并找到相遇的節(jié)點 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,確定是一個有環(huán)的鏈表; } slow = slow.next; fast = fast.next; if(fast!=null){ fast = fast.next; } } return null; }
3.尋找入口節(jié)點
先讓快指針先走環(huán)的節(jié)點的個數(shù)步,在讓慢指針開始走,如果兩個指針相遇的話,那么相遇的節(jié)點必然是環(huán)的入口節(jié)點
代碼如下:
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ù)測試;
ublic 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如何確定一個鏈表有環(huán)及入口節(jié)點的詳細內(nèi)容,更多關(guān)于java鏈表及入口節(jié)點的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
Spring Cloud Feign實現(xiàn)動態(tài)URL
本文主要介紹了Spring Cloud Feign實現(xiàn)動態(tài)URL,文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下2022-02-02springboot如何獲取application.yml里值的方法
這篇文章主要介紹了springboot如何獲取application.yml里的值,文章圍繞主題相關(guān)自資料展開詳細的內(nèi)容介紹,具有一定的參考價值,需要的小伙伴可以參考一下2022-04-04