JAVA高级面试进阶训练营视频教程

admin

单链表是否有环的问题经常在面试中遇到，一般面试中会要求空间为O(1);再者求若有环，则求环产生时的起始位置。

下面采用java实现。

//单链表
class ListNode{
     int val;
     ListNode next;
     ListNode(int x){
         val=x;
         next=null;
     }
}
public class SearchCycleNode{
    ListNode equalListNode=null;//来记录判断有环时出现的相等的时的节点,姑且叫"相遇"节点。
　　//从"相遇"节点出发，第一个可达的节点（从单链表的头节点开始）即是单链表的环产生的起始位置
    public ListNode detectCycle(ListNode head) {
            if(!hasCycle(head)) return null;
            ListNode p=head;
            while(!isReach(p)){
                p=p.next;
            }
            return p;
            
    }
   //判断从相遇的节点到 head节点可达性
    private boolean isReach(ListNode head){
         if(head==equalListNode)return true;
          ListNode p=equalListNode.next;
        while(p!=equalListNode){
           if(p==head)return true;
           p=p.next;
        }
        return false;
    }
   //判断是否有环，通过一个指针p走一步，一个指针q走两步，如果能出现p=q的情况，则有环，并记录p为"相遇"节点。
    private boolean hasCycle(ListNode head) {
           if(head==null)return false;
           if(head.next==null)return false;
           ListNode p=head;
           ListNode q=head.next;
           while(p!=q){
              if(p.next==null)return false;
              p=p.next;
              if(q.next==null)return false;
              if(q.next.next==null)return false;
              q=q.next.next;
           }
           equalListNode=p;
           return true;
           
      }
}