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;

     }

}