首页 > 代码库 > 单链表是否有环的问题解决与讨论(java实现)

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

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

 

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