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

el/2024/7/13 11:51:45

题目描述

一个链表中包含环,请找出该链表的环的入口结点。要求不能使用额外的空间。可以参见剑指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://www.ngui.cc/el/5179135.html

相关文章

目标检测中mAP的定义

作者:nowgood 链接:https://www.zhihu.com/question/53405779/answer/506000532 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 目标检测中衡量识别精度的指标是mAP(mean averag…

java jdk中的动态代理和Cglib中的动态代理的解析

为什么要用动态代理? 因为静态代理需要额外编写代理类,对于每一个要代理的对象,都要书写一个额外的代理类。 使用代理的原因? 有些类是不能够直接访问的或者有些访问要经过特殊处理。 1. Java JDK中的动态代理 java jdk中的动态…

求1+2+3+4+5+..+n

题目描述 求123...n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。 其主要思想是递归,这个程序很美。 package cn.cqu.edu;public class Sum_Solution1 {public int Sum_Solution(in…

tomcat运行java web时,报这个错:org.springframework.beans.factory.BeanCreationException

具体出错信息如下: 严重: StandardWrapper.Throwable org.springframework.beans.factory.BeanCreationException: Error creating bean with name userController: Injection of autowired dependencies failed; nested exception is org.springframework.beans.factory.Bea…

eclipse下springmvc+spring+maven+mybatis+mysql的搭建,并实现增删改查

eclipse下SpringMVC+Maven+Mybatis+MySQL项目搭建 这篇文章主要讲解在eclipse环境下SpringMVC+Maven+Mybatis+MySQL的项目搭建过程。 创建Maven工程。右击-->New->Other 点击->Manven Porject 点击->勾选快速框架 输入项目名,包(Packaging,如果只是普通的项目,…

大数据笔试面试题

问题: 有一个包含20亿个全是32位整数的大文件,在其中找到出现次数最多的数,但是内存限制只有2G. 解题思路:先将这个20亿个整数进行哈希分流,比如说分别分流到16个小文件中,然后用哈希表分别计算出每一个小…

c/c++中动态内存分配与回收与从void*类型隐式转换为int*类型

最常见的差异之一是,C允许从void*隐式转换到其它的指针类型,但C++不允许。下列是有效的C代码。从void*类型隐式转换为int*类型,但要使其在C和C++两者皆能运作,就需要使用显式转换。 c语言版本的: #include <stdio.h> #include <stdlib.h>#define high 2 #de…

c语言数据类型本质及其分析

c语言的数据类型如下&#xff1a; 数据类型的本质是固定内存大小区域的别名。数据类型的作用是编译器预算对象&#xff08;变量&#xff09;的内存大小&#xff0c;从而为其分配。求数据类型的大小可以用sizeof&#xff08;int&#xff09;。数据类型的别名可以用typedef来自定…

c语言中的内存4区域模型(堆,栈,全局区,代码区)

理解c语言的4个内存区域模型&#xff0c;对于学习好c语言是十分重要的。c语言的内存4区域模型如下&#xff1a;