剑指Offer—编程题56(链表中环的入口地址)

2024-06-24 08:32

本文主要是介绍剑指Offer—编程题56(链表中环的入口地址),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:一个链表中包含环,如何找出环的入口结点?


解题思路

  可以用两个指针来解决这个问题。先定义两个指针P1和P2指向链表的头结点。如果链表中环有n个结点,指针P1在链表上向前移动n步,然后两个指针以相同的速度向前移动。当第二个指针指向环的入口结点时,第一个指针已经围绕着环走了一圈又回到了入口结点。 
  剩下的问题就是如何得到环中结点的数目。我们在面试题15的第二个相关题目时用到了一快一慢的两个指针。如果两个指针相遇,表明链表中存在环。两个指针相遇的结点一定是在环中。可以从这个结点出发,一边继续向前移动一边计数,当再次回到这个结点时就可以得到环中结点数了。

结点定义

private static class ListNode {private int val;private ListNode next;public ListNode() {}public ListNode(int val) {this.val = val;}@Overridepublic String toString() {return val +"";}}

代码实现

public class Test56 {private static class ListNode {private int val;private ListNode next;public ListNode() {}public ListNode(int val) {this.val = val;}@Overridepublic String toString() {return val +"";}}public static ListNode meetingNode(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (fast == slow) {break;}}// 链表中没有环if (fast == null || fast.next == null) {return null;}// fast重新指向第一个结点fast = head;while (fast != slow) {fast = fast.next;slow = slow.next;}return fast;}public static void main(String[] args) {test01();test02();test03();}// 1->2->3->4->5->6private static void test01() {ListNode n1 = new ListNode(1);ListNode n2 = new ListNode(2);ListNode n3 = new ListNode(3);ListNode n4 = new ListNode(4);ListNode n5 = new ListNode(5);ListNode n6 = new ListNode(6);n1.next = n2;n2.next = n3;n3.next = n4;n4.next = n5;n5.next = n6;System.out.println(meetingNode(n1));}// 1->2->3->4->5->6//       ^        |//       |        |//       +--------+private static void test02() {ListNode n1 = new ListNode(1);ListNode n2 = new ListNode(2);ListNode n3 = new ListNode(3);ListNode n4 = new ListNode(4);ListNode n5 = new ListNode(5);ListNode n6 = new ListNode(6);n1.next = n2;n2.next = n3;n3.next = n4;n4.next = n5;n5.next = n6;n6.next = n3;System.out.println(meetingNode(n1));}// 1->2->3->4->5->6 <-+//                |   |//                +---+private static void test03() {ListNode n1 = new ListNode(1);ListNode n2 = new ListNode(2);ListNode n3 = new ListNode(3);ListNode n4 = new ListNode(4);ListNode n5 = new ListNode(5);ListNode n6 = new ListNode(6);n1.next = n2;n2.next = n3;n3.next = n4;n4.next = n5;n5.next = n6;n6.next = n6;System.out.println(meetingNode(n1));}
}

运行结果

这里写图片描述

这篇关于剑指Offer—编程题56(链表中环的入口地址)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定

Ubuntu固定虚拟机ip地址的方法教程

《Ubuntu固定虚拟机ip地址的方法教程》本文详细介绍了如何在Ubuntu虚拟机中固定IP地址,包括检查和编辑`/etc/apt/sources.list`文件、更新网络配置文件以及使用Networ... 1、由于虚拟机网络是桥接,所以ip地址会不停地变化,接下来我们就讲述ip如何固定 2、如果apt安

查询SQL Server数据库服务器IP地址的多种有效方法

《查询SQLServer数据库服务器IP地址的多种有效方法》作为数据库管理员或开发人员,了解如何查询SQLServer数据库服务器的IP地址是一项重要技能,本文将介绍几种简单而有效的方法,帮助你轻松... 目录使用T-SQL查询方法1:使用系统函数方法2:使用系统视图使用SQL Server Configu

使用Java实现获取客户端IP地址

《使用Java实现获取客户端IP地址》这篇文章主要为大家详细介绍了如何使用Java实现获取客户端IP地址,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 首先是获取 IP,直接上代码import org.springframework.web.context.request.Requ

Linux环境变量&&进程地址空间详解

《Linux环境变量&&进程地址空间详解》本文介绍了Linux环境变量、命令行参数、进程地址空间以及Linux内核进程调度队列的相关知识,环境变量是系统运行环境的参数,命令行参数用于传递给程序的参数,... 目录一、初步认识环境变量1.1常见的环境变量1.2环境变量的基本概念二、命令行参数2.1通过命令编程

C#多线程编程中导致死锁的常见陷阱和避免方法

《C#多线程编程中导致死锁的常见陷阱和避免方法》在C#多线程编程中,死锁(Deadlock)是一种常见的、令人头疼的错误,死锁通常发生在多个线程试图获取多个资源的锁时,导致相互等待对方释放资源,最终形... 目录引言1. 什么是死锁?死锁的典型条件:2. 导致死锁的常见原因2.1 锁的顺序问题错误示例:不同

C++实现获取本机MAC地址与IP地址

《C++实现获取本机MAC地址与IP地址》这篇文章主要为大家详细介绍了C++实现获取本机MAC地址与IP地址的两种方式,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 实际工作中,项目上常常需要获取本机的IP地址和MAC地址,在此使用两种方案获取1.MFC中获取IP和MAC地址获取

C/C++通过IP获取局域网网卡MAC地址

《C/C++通过IP获取局域网网卡MAC地址》这篇文章主要为大家详细介绍了C++如何通过Win32API函数SendARP从IP地址获取局域网内网卡的MAC地址,感兴趣的小伙伴可以跟随小编一起学习一下... C/C++通过IP获取局域网网卡MAC地址通过win32 SendARP获取MAC地址代码#i

PyCharm接入DeepSeek实现AI编程的操作流程

《PyCharm接入DeepSeek实现AI编程的操作流程》DeepSeek是一家专注于人工智能技术研发的公司,致力于开发高性能、低成本的AI模型,接下来,我们把DeepSeek接入到PyCharm中... 目录引言效果演示创建API key在PyCharm中下载Continue插件配置Continue引言

C#反射编程之GetConstructor()方法解读

《C#反射编程之GetConstructor()方法解读》C#中Type类的GetConstructor()方法用于获取指定类型的构造函数,该方法有多个重载版本,可以根据不同的参数获取不同特性的构造函... 目录C# GetConstructor()方法有4个重载以GetConstructor(Type[]