首页 > 代码库 > 单链表是否有环的问题解决与讨论(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实现)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。