leetcode141.环形链表,142环形链表ii

server/2025/3/4 6:00:16/

目录

  • 问题描述
  • 示例
    • 提示
  • 具体思路
    • 思路一
  • 代码实现
  • 问题描述
  • 具体思路
    • 思路一
    • 思路二

问题描述

给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。

题目链接:环形链表1

示例

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

提示

  链表中节点的数目范围是 [0, 104]
  -105 <= Node.val <= 105
  pos 为 -1 或者链表中的一个 有效索引 。

具体思路

思路一

在这里插入图片描述

环形链表1
1、slow和fast一定会相遇吗?
一定会,fast会先进环,slow会后进环,假设slow进环时,slow和fast之间的距离为N
slow进环以后,fast开始追击slow,slow每走1步,fast每走2步,他们之间距离缩小1。
N N-1 N-2 N-3 N-4 … 2 1 0

2、slow走1步,fast走n(3/4/5…)步可以吗?(n>2)
不一定,fast会先进环,slow会后进环,假设slow进环时,slow和fast之间的距离为N
slow进环以后,fast开始追击slow,slow每走1步,fast每走3步,他们之间距离缩小2。
N N-2 N-4 N-6 … 4 2 0
N是偶数就会相遇。N是奇数就会错过,会进入新一轮的追击,slow和fast的距离变成C-1(假设C是环的长度)
如果C-1是偶数那么下一轮可以追上
如果C-1是奇数那么永远追不上

代码实现

//思路1
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {struct ListNode* slow=head;struct ListNode* fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast)return true;}return false;
}

问题描述

给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表

题目链接:环形链表2

具体思路

思路一

在这里插入图片描述
转换为相交链表的问题,将meetNext=meet->next,meet->next=NULL。然后使用相交链表的问题求解相交的交点

思路二

在这里插入图片描述

环形链表2
fast走的路程是slow的2倍
假设:链表头–环入口点距离:L
环入口点–距离点距离:X
环的长度:C

slow走的路程是多少:L+X -> 分析,有没有可能slow进环转了几圈才追上?不可能!1圈之内,fast必然追上slow,因为他们之间距离每次缩小1,不会错过,slow走1圈,fast都走了2圈了,肯定追上了。

fast走的路程是多少:L+nC+X

2*(L+X)=L+nC+X
L+X=nC
L=nC-X
n是slow进环前,fast在环里面转的圈数

所以一个指针从相遇点走,一个指针从链表头开始走,他们会在入口点相遇

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slow=head;struct ListNode* fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){struct ListNode* meet=slow;while(head!=meet){head=head->next;meet=meet->next;}return meet;}}return NULL;
}

http://www.ppmy.cn/server/172266.html

相关文章

自学微信小程序的第六天

DAY6 1、使用录音API首先需要通过wx.getRecorderManager()方法获取到一个RecorderManager实例,该实例是一个全局唯一的录音管理器,用于实现录音功能。 表32:RecorderManager实例的常用方法 方法名称 说明 start() 开始录音 pause() 暂停录音 resume() 继续录音 stop() 停止…

10种方法教你又小又清晰地压缩视频

视频压缩是有可能会损失画质的&#xff0c;但也可以通过一些方法尽量减少画质损失。在有效压缩视频大小的同时&#xff0c;尽量控制视频压缩画质在人眼无法察觉的范围内。下面就从10个角度向大家介绍10个不同的视频压缩方法&#xff0c;并推荐相关的视频压缩软件&#xff0c;整…

AI赋能视频创作:零基础也能玩转短视频制作

在短视频风靡的今天&#xff0c;你是否也渴望创作出属于自己的精彩作品&#xff0c;却苦于没有专业设备和剪辑技巧&#xff1f;别担心&#xff0c;AI技术的飞速发展为我们带来了全新的解决方案&#xff01;即使你是零基础小白&#xff0c;也能借助AI工具轻松合成小视频&#xf…

DeepSeek R1满血+火山引擎详细教程

DeepSeek R1满血火山引擎详细教程 一、安装Cherry Studio。 Cherry Studio AI 是一款强大的多模型 AI 助手,支持 iOS、macOS 和 Windows 平台。可以快速切换多个先进的 LLM 模型,提升工作学习效率。下载地址 https://cherry-ai.com/ 认准官网&#xff0c;无强制注册。 这…

FPGA的ram Xilinx的IP Block Memory Generator

做过设计的对memory都比较熟悉了&#xff0c;在Asic设计中通常是rom&#xff0c;ram&#xff0c;那这些rom&#xff0c;ram在FPGA的模式下面怎么做呢&#xff0c;有两种方法&#xff0c;一种就是自己写代码&#xff0c;用寄存器去搭&#xff0c;搭好后需要指定综合成block ram&…

Sparsely-Gated Mixture-of-Experts Layer (MoE)论文解读与Pytorch代码实现

MoE解析 阅读论文&#xff1a;https://arxiv.org/pdf/1701.06538 OUTRAGEOUSLY LARGE NEURAL NETWORKS:THE SPARSELY-GATED MIXTURE-OF-EXPERTS LAYER 本文介绍了一种名为Sparsely-Gated Mixture-of-Experts Layer (MoE) 的神经网络组件&#xff0c;旨在通过条件计算&#xf…

Ubuntu 下 nginx-1.24.0 源码分析 - ngx_init_cycle 函数 - 详解(8)

详解&#xff08;8&#xff09; 初始化模块配置上下文&#xff08;conf_ctx&#xff09; cycle->conf_ctx ngx_pcalloc(pool, ngx_max_module * sizeof(void *));if (cycle->conf_ctx NULL) {ngx_destroy_pool(pool);return NULL;}1 分配模块配置上下文数组 cycle->…

kafka stream对比flink

Kafka Streams 和 Apache Flink 虽然都支持实时计算&#xff0c;但它们的定位、架构和适用场景存在显著差异。选择哪一个取决于具体的需求、场景和技术栈。以下是两者的核心区别和适用场景分析&#xff1a; 1. 定位与架构差异 Kafka Streams 定位&#xff1a;轻量级库&#x…