本文共 1101 字，大约阅读时间需要 3 分钟。

题目描述

一个链表中包含环，请找出该链表的环的入口结点。要求不能使用额外的空间。可以参见剑指offer上的原题。代码如下：

package cn.cqu.edu;public class NodeOfLoop {		class ListNode {	    int val;	    ListNode next = null;	    ListNode(int val) {	        this.val = val;	    }	}		//先判断有没有形成环,返回环中的任意一个节点	public ListNode isLoop(ListNode pHead)	{		if(pHead==null)		{			return null;		}				ListNode mSlow=pHead.next;		ListNode mFast=pHead.next;		if(mFast==null)		{			return null;		}				mFast=mFast.next;				while(mFast!=null && mSlow!=null)		{			if(mFast==mSlow)			{				return mFast;			}			mSlow=mSlow.next;			mFast=mFast.next;			if(mFast==null)			{				break;			}			mFast=mFast.next;		}						return null;	}		public ListNode EntryNodeOfLoop(ListNode pHead)    {		ListNode oop=isLoop(pHead);		if(oop==null)		{			return null;  //没有形成环		}				int cnt=1; //计算环的个数有多少个		ListNode temp=oop;		oop=oop.next;		while(oop!=temp)		{			cnt++;			oop=oop.next;		}				ListNode p1=pHead;		ListNode p2=pHead;				while(cnt>0)		{			p1=p1.next;			cnt--;		}				while(p1!=p2)		{			p1=p1.next;			p2=p2.next;		}				return p1;				            }	public static void main(String[] args) {							}}

转载地址：http://xdkmi.baihongyu.com/