剑指offer----链表中环的入口节点----java实现

2024-01-15 23:58

本文主要是介绍剑指offer----链表中环的入口节点----java实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一个链表中包含环,请找出该链表的环的入口结点。

此问题包含两个步骤:

(1)判断链表中是否有环

(2)找出环

一、

1)选择快慢指针,让快指针每次走两步,慢指针每次走一步,若是单链表中有环的话,那么两个指针会相遇,即指向的相同的节点来判断。

2)当相遇的时候,慢指针在环中走了k步,设环之外的部分长为x,环的长度为n,则快指针一共走了 x+m*n+k步,(m为快指针在环中走的圈数),慢指针一共走了x+k步,因为快指针的速度是慢指针的两倍。那么可以得到2(x+k)=x+m*n+k;得到x为m*n-k ,慢指针在圈中还剩下的步数n-k;

二、

让快指针从头开始,两个指针每次都走一步,当快指针走了想x(m*n-k)步的时候,到达环的入口,慢指针在圈中走m-1圈加k步的时候,也到达环入口那个节点,两个指针再次相遇,此刻的节点就是环的入口的节点。

 

 

 

/*public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}
*/
public class Solution 
{public ListNode EntryNodeOfLoop(ListNode pHead){if(pHead == null || pHead.next == null)return null;ListNode fast = pHead;//快指针每次走两步ListNode slow = pHead;//每次走一步while(fast!=null && fast.next !=null)//因为fast每次要走两步,所有需要判断fast的下一个是否为空{slow = slow.next;fast = fast.next.next;//判断是否相遇 相遇后让快指针从头开始走,每次都是走一步,第二次相遇的节点就是环的入口if(fast.val == slow.val){fast = pHead;while(fast != slow){fast = fast.next;slow = slow.next;}}if(fast == slow){return slow;}}return null;//要是没有相遇,此链表没有环返回空}
}

 

 

 

 

 

这类问题还可以延伸出来求

(1)环的长度、(2)整个链表的长度、(3)两个无环链表第一次相交的公共节点

(1)环的长度,当快慢指针第一次相遇的时候,把该节点保存下来,让慢指针接着走,当再次到达刚才相遇的节点时所走过的步数就是环的长度。

(2)利用第二步求出环以外的长度再加上环的长度,就是整个链表的长度

(3)先分别求出两个链表的长度,让长的链表先走两个链表长度差的步数,再让两个链表一起走,当走到节点值相同的那个节点时,就是相交的第一个公共节点。

 

这篇关于剑指offer----链表中环的入口节点----java实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/610642

相关文章

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类,它们之间的依赖,构建起了整个框架。想要理解整个架构,最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文(security context)的信息。当前操作的用户是谁,该用户是否已经被认证,他拥有哪些角色权限…这些都被保

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu