本文主要是介绍判断单链表有环，存在的话找到环的入口，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
如果单链表存在环的话,必然是在链尾。如果不在链尾的话，会出现一个链表结点有两个next的情况。
可设置两个节点指针first和second, first速度为2, second的速度为1,如果链表存在环，则first到达环内后一直在环内循环转圈，总会有一个时间first会和second第一次相遇，此时，他们路程的差为环的长度，而这时second还没到达链尾，以为如果second已经到达链尾，设second的路程为l，则first的路程为2l，2l-l=l，会推出l>r（即环的长度），而此时为第一次相遇，l不可能大于r，因此这时second还没到达链尾。
设如图，x为链表起点到环的入口的距离，y为环入口到第一次相遇点的距离，r为环的长度。则有
first的路程为x+y
second的路程为2(x+y)
2(x+y)-(x+y)=r => x+y=r => x=r-y
则有，此时设置一个指针entry从链表头出发，与second的速度相同，当entry与second相等时，此entry为环的入口。
代码如下
链表节点类
/**
* 链表节点数据结构
* @author zs
*/
publicclass LinkNode {
publicint id;
publicLinkNode next;
publicLinkNode(){}
publicLinkNode(int id){
this.id=id;
}
publicLinkNode(int id,LinkNode next){
this.id=id;
this.next=next;
}
}
链表操作类：生成链表，制造环
importjava.util.HashMap;
importjava.util.List;
publicclass LinkNodeHelper {
/**
* 将LinkNode的节点串成链表
* @paramlist 存储链表节点的列表
*/
publicvoid putIntoLinkList(List<LinkNode> list){
for(int i = 0; i < list.size()-1; i++) {
list.get(i).next=list.get(i+1);
}
}
/**
* 制造环
* @paramroot 链表头
* @paramk 链表环出现的位置
*/
publicLinkNode makeCircle(List<LinkNode> list,int k){
list.get(list.size()-1).next=list.get(k);
returnlist.get(k);
}
}
寻找环的算法代码
importjava.util.ArrayList;
importjava.util.List;
/**
* 找到判断单链表是否存在环，若存在返回环与主链的第一个交点
* @author Administrator *
*/
publicclass FindCircle {
publicLinkNode findEntry(LinkNode root){
if(root==null||root.next==null) {
returnnull;
}
LinkNodefirst=root;
LinkNodesecond=root;
LinkNodeentry=null;
booleanisCircle=false;
while(first!=null&&second!=null&&!isCircle){
first=first.next.next;
second=second.next;
if(second==first) {
isCircle=true;
}
}
if(isCircle==true) {
entry=root;
while(entry!=second){
entry=entry.next;
second=second.next;
}
}
returnentry;
}
publicstatic void main(String[] args) {
List<LinkNode>list=new ArrayList<LinkNode>();
for(int i = 0; i < 20; i++) {
LinkNodenode=new LinkNode(i);
list.add(node);
}
LinkNodeHelpernodeHelper=new LinkNodeHelper();
nodeHelper.putIntoLinkList(list);
FindCirclefindCircle=new FindCircle();
LinkNodeentryNode=findCircle.findEntry(list.get(0));
if(entryNode==null) {
System.out.println("haven'tfound!");
intk=6;
LinkNodetrueEntry=nodeHelper.makeCircle(list, k);
System.out.println("makecircle, entry id is "+k);
entryNode=findCircle.findEntry(list.get(0));
if(entryNode!=null&&entryNode.id==trueEntry.id) {
System.out.println("findentry: id="+entryNode.id);
}
}else{
System.out.println("found!"+entryNode.id);
}
}
}
这篇关于判断单链表有环，存在的话找到环的入口的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
