[php]代码库
/*
*单链表的结点类
*/
class LNode{
//为了简化访问单链表,结点中的数据项的访问权限都设为public
public int data;
public LNode next;
}
class LinkListUtli {
//当单链表中没有环时返回null,有环时返回环的入口结点
public static LNode searchEntranceNode(LNode L)
{
LNode slow=L;//p表示从头结点开始每次往后走一步的指针
LNode fast=L;//q表示从头结点开始每次往后走两步的指针
while(fast !=null && fast.next !=null)
{
if(slow==fast) break;//p与q相等,单链表有环
slow=slow.next;
fast=fast.next.next;
}
if(fast==null || fast.next==null) return null;
// 重新遍历,寻找环的入口点
slow=L;
while(slow!=fast)
{
slow=slow.next;
fast=fast.next;
}
return slow;
}
}