java如何確定一個(gè)鏈表有環(huán)及入口節(jié)點(diǎn)
如何確定一個(gè)鏈表有環(huán),入口節(jié)點(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; } //無(wú)參構(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.編寫(xiě)判斷是否存在環(huán)
如果存在,則返回這個(gè)節(jié)點(diǎn),如果不存在則返回null,定義快慢指針,如果快的追上了慢的指針,那么這個(gè)鏈表必存在環(huán),如果沒(méi)有追上,或者都為null,那么這個(gè)鏈表沒(méi)有環(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ù)步,在讓慢指針開(kāi)始走,如果兩個(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è)試;
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如何確定一個(gè)鏈表有環(huán)及入口節(jié)點(diǎn)的詳細(xì)內(nèi)容,更多關(guān)于java鏈表及入口節(jié)點(diǎn)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
Java中JDK動(dòng)態(tài)代理的超詳細(xì)講解
JDK 的動(dòng)態(tài)代理是基于攔截器和反射來(lái)實(shí)現(xiàn)的,JDK代理是不需要第三方庫(kù)支持的,只需要JDK環(huán)境就可以進(jìn)行代理,下面這篇文章主要給大家介紹了關(guān)于Java中JDK動(dòng)態(tài)代理的超詳細(xì)講解,需要的朋友可以參考下2022-10-10springboot項(xiàng)目中配置redis詳細(xì)的教程
Redis是一種高性能的鍵值存儲(chǔ)數(shù)據(jù)庫(kù),而Spring Boot是一個(gè)簡(jiǎn)化了開(kāi)發(fā)過(guò)程的Java框架,這篇文章主要給大家介紹了關(guān)于springboot項(xiàng)目中配置redis詳細(xì)的教程,文中通過(guò)代碼介紹的非常詳細(xì),需要的朋友可以參考下2024-04-04Spring Cloud Feign實(shí)現(xiàn)動(dòng)態(tài)URL
本文主要介紹了Spring Cloud Feign實(shí)現(xiàn)動(dòng)態(tài)URL,文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-02-02Java多種經(jīng)典排序算法(含動(dòng)態(tài)圖)
排序算法是老生常談的了,但是在面試中也有會(huì)被問(wèn)到,例如有時(shí)候,在考察算法能力的時(shí)候,不讓你寫(xiě)算法,就讓你描述一下,某個(gè)排序算法的思想以及時(shí)間復(fù)雜度或空間復(fù)雜度。我就遇到過(guò),直接問(wèn)快排的,所以這次我就總結(jié)梳理一下經(jīng)典的十大排序算法以及它們的模板代碼2021-04-04Java預(yù)覽PDF時(shí)的文件名稱問(wèn)題及解決
這篇文章主要介紹了Java預(yù)覽PDF時(shí)的文件名稱問(wèn)題及解決方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-01-01springboot2.0整合logback日志的詳細(xì)代碼
這篇文章主要介紹了springboot2.0整合logback日志的應(yīng)用場(chǎng)景分析,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-02-02springboot如何獲取application.yml里值的方法
這篇文章主要介紹了springboot如何獲取application.yml里的值,文章圍繞主題相關(guān)自資料展開(kāi)詳細(xì)的內(nèi)容介紹,具有一定的參考價(jià)值,需要的小伙伴可以參考一下2022-04-04springboot自動(dòng)配置沒(méi)有生效的問(wèn)題定位(條件斷點(diǎn))
這篇文章主要介紹了springboot自動(dòng)配置未生效問(wèn)題定位,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,下面我們來(lái)學(xué)習(xí)一下吧2019-06-06