java實現(xiàn)單鏈表中是否有環(huán)的方法詳解
這是一道微軟經(jīng)典筆試題，就是兩個指針h1,h2都從頭開始遍歷單鏈表，h1每次向前走1步，h2每次向前走2步，如果h2碰到了NULL，說明環(huán)不存在；如果h2碰到本應在身后的h1說明環(huán)存在（也就是發(fā)生了套圈）。
如果環(huán)不存在，一定是h2先碰到NULL：
如果環(huán)存在，h2與h1一定會相遇，而且相遇的點在環(huán)內(nèi)：h2比h1遍歷的速度快，一定不會在開始的那段非環(huán)的鏈表部分相遇，所以當h1,h2都進入環(huán)后，h2每次移動都會使h2與h1之間在前進方向上的差距縮小1，最后，會使得h1和h2差距減少為0，也即相遇
package org.myorg;
public class Test{
public static boolean isExsitLoop(SingleList a) {
Node<T> slow = a.head;
Node<T> fast = a.head; while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast)
return true;
}
return false;
}
public static void main(String args[]){
SingleList list = new SingleList();
for(int i=0;i<100;i++){
list.add(i);
}
System.out.print(SingleList.isExistingLoop(list));
}
}
package org.myorg;
public class Node{
public Object data; //節(jié)點存儲的數(shù)據(jù)對象
public Node next; //指向下一個節(jié)點的引用
public Node(Object value){
this.data = value;
}
public Node(){
this.data = null;
this.next = null;
}
}
package org.myorg;
public class SingleList{
private int size;
private Node head;
private void init(){
this.size = 0;
this.head = new Node();
}
public SingleList(){
init();
}
public boolean contains(Object value){
boolean flag = false;
Node p = head.next;
while(p!=null){
if(value.equals(p.data)){
flag = true;
break;
}else(
p = p.next;
)
}
return flag;
}
public boolean add(Object value){
if(contains(value))
return false;
else{
Node p = new Node(value);
p.next=head.next;
head.next = p;
size++;
}
return true;
}
}
相關文章
MybatisPlus 不修改全局策略和字段注解如何將字段更新為null
這篇文章主要介紹了MybatisPlus 不修改全局策略和字段注解如何將字段更新為null,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-04-04
application.yml文件中如何開啟mybatis自動駝峰映射
這篇文章主要介紹了application.yml文件中開啟mybatis自動駝峰映射的方法,本文通過示例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2023-08-08
這篇文章主要介紹了java中設計模式之適配器模式的相關資料,適配器模式將一個類的接口轉換成客戶期望的另一個接口。適配器讓原本不兼容的類可以合作得親密無間,需要的朋友可以參考下2017-09-09
這篇文章主要給大家介紹了關于JAVA中取整數(shù)的4種方法,在java的Math類中,提供了許許多多的和數(shù)學計算有關的方法,其中也包括取整的,需要的朋友可以參考下2023-07-07
本篇文章主要給大家講述了作為JAVA程序員如何能寫出高效的代碼以及運行效率更高的代碼，一起學習分享下吧。2017-12-12
這篇文章主要介紹了java中JSP頁面技術之EL表達式概念作用以及語法等的使用，需要的朋友可以參考2017-04-04
Java?ArrayList實現(xiàn)刪除指定位置的元素
目標：list中有0到39共40個元素，刪除其中索引是10、20、30的元素。本文為大家整理了三個不同的方法，感興趣的小伙伴可以跟隨小編一起學習一下2023-01-01
SpringBoot+slf4j線程池全鏈路調(diào)用日志跟蹤問題及解決思路(二)
本文主要給大家介紹如何實現(xiàn)子線程中的traceId日志跟蹤，本文通過封裝Callable為例給大家介紹的非常詳細，需要的朋友一起看看吧2021-05-05
這篇文章主要介紹了java 讀取本地文件實例詳解的相關資料,需要的朋友可以參考下2017-05-05
Java中@RequiredArgsConstructor注解的基本用法
這篇文章主要介紹了Java中@RequiredArgsConstructor注解的基本用法,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-09-09