問題1：給定一個單鏈表，判斷鏈表中是否有環
問題2：給定一個鏈表，回傳鏈表開始入環的第一個節點，如果無環，則回傳null
class Node{
public int data;
Node next;
public Node(int data){
this.data=data;
this.next=null;
}
}
public class linkedList {
/*給定一個鏈表，判斷鏈表中是否有環
思路： 如果鏈表有環的話，定義兩個節點fast,slow，讓fast一次走兩步，slow一次走一步；
如果能相交，即fast=slow，說明有交點，且如果有環，節點的next也不會為空
*/
public Node head;
public boolean hasCycle(){
Node fast=this.head;
Node slow=this.head;
while (fast!=null&&fast.next!=null){//如果把fast.next寫下前面，一旦fast為空，則會空指標例外
fast=fast.next.next;
slow=slow.next;
if(fast==slow){
return true;
}
}
return false;
}
//給定一個鏈表，回傳鏈表開始入環的第一個節點，如果無環，則回傳null
public Node detectCycle(){
/*定義fast與slow,fast前進2格，slow前進一格，如果有交點的話，fast與slow第一次相遇時，fast的路程為slow的2倍，
如設從頭節點到入環節點的距離為X，令入環節點到fast,slow第一次相遇距離為Y，環的總長度為C的話;可得公式：2（X+Y）=X+Y+NC；
得X=NC-Y，令N等于1，X=C-Y;此時讓slow從頭節點開始走，當于速度相同的fast相遇時，則為入環的節點，
*/
Node fast=this.head;
Node slow=this.head;
while (fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow){//第一次相遇
break;
}
}
if(fast==null&&fast.next==null){
return null;
}
//此時讓slow從頭節點開始，與fast以相同速度前進，遇到則為入環的第一個節點
slow=this.head;
while (fast!=slow){
fast=fast.next;
slow=slow.next;
}
return slow;
}
}轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/291640.html
標籤：其他
上一篇：資料結構OJ題——移除鏈表元素
下一篇：計算機網路-6-應用層