Java之單鏈表問題解決案例講解

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;
    }
}