单链表是否有环的问题解决与讨论（java实现）

刺骨的言语ヽ痛彻心扉 2021-12-10 17:29 134阅读 0赞

单链表是否有环的问题经常在面试中遇到，一般面试中会要求空间为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;
               
          }
    }

转载于:https://www.cnblogs.com/big-sun/p/4077555.html