题目描述 一个链表中包含环，请找出该链表的环的入口结点。要求不能使用额外的空间。

本文主要是介绍题目描述 一个链表中包含环，请找出该链表的环的入口结点。要求不能使用额外的空间。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

一个链表中包含环，请找出该链表的环的入口结点。要求不能使用额外的空间。可以参见剑指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) {}}

 

这篇关于题目描述 一个链表中包含环，请找出该链表的环的入口结点。要求不能使用额外的空间。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---