面试经典算法系列之链表2 -- 环形链表

面试经典算法8-环形链表

LeetCode.141
公众号:阿Q技术站

问题描述

给你一个链表的头节点 head ,判断链表中是否有环。

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

如果链表中存在环 ,则返回 true 。 否则,返回 false

示例 1:

img

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

img

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

img

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

提示:

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

**进阶:**你能用 O(1)(即,常量)内存解决此问题吗?

思路

  1. 定义两个指针 slowfast,初始时都指向链表的头节点 head
  2. slow 每次向后移动一个节点,fast 每次向后移动两个节点。这样,如果链表中有环,fast 最终会追上 slow
  3. 如果 fastnullptr 或者 fast->nextnullptr,则说明链表中不存在环,返回 false
  4. 如果 fastslow 相遇,则说明链表中存在环,返回 true

图解

这里根据示例1给大家做一个图解演示。

  1. 初始化,定义两个指针 slowfast,初始时都指向链表的头节点 head

image-20240130212914475

  1. slow 每次向后移动一个节点,fast 每次向后移动两个节点。

image-20240130213848438

  1. 继续移动

image-20240130214021817

  1. 继续移动

image-20240130214125618

此时, fastslow 相遇,说明链表中存在环,返回true。

如果 fastnullptr 或者 fast->nextnullptr,则说明链表中不存在环,返回 false

参考代码

C++
#include <iostream>

// 定义链表节点结构
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    bool hasCycle(ListNode *head) {
        // 定义快慢指针,并初始化为链表头节点
        ListNode *slow = head;
        ListNode *fast = head;

        // 使用快慢指针判断链表中是否存在环
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;       // 慢指针每次移动一步
            fast = fast->next->next; // 快指针每次移动两步
            if (slow == fast) {      // 如果快慢指针相遇,说明存在环
                return true;
            }
        }

        // 如果快指针到达链表尾部,说明不存在环
        return false;
    }
};

int main() {
    // 创建一个有环的链表
    ListNode *head = new ListNode(3);
    head->next = new ListNode(2);
    head->next->next = new ListNode(0);
    head->next->next->next = new ListNode(-4);
    head->next->next->next->next = head->next; // 尾节点连接到第二个节点,形成环

    Solution sol;
    std::cout << std::boolalpha << sol.hasCycle(head) << std::endl; // 输出 true,表示链表中存在环

    // 释放链表内存
    ListNode *curr = head;
    while (curr != nullptr) {
        ListNode *temp = curr;
        curr = curr->next;
        delete temp;
    }

    return 0;
}
Java
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        // 定义快慢指针,并初始化为链表头节点
        ListNode slow = head;
        ListNode fast = head;

        // 使用快慢指针判断链表中是否存在环
        while (fast != null && fast.next != null) {
            slow = slow.next;       // 慢指针每次移动一步
            fast = fast.next.next;  // 快指针每次移动两步
            if (slow == fast) {     // 如果快慢指针相遇,说明存在环
                return true;
            }
        }

        // 如果快指针到达链表尾部,说明不存在环
        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        // 创建一个有环的链表
        ListNode head = new ListNode(3);
        head.next = new ListNode(2);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(-4);
        head.next.next.next.next = head.next; // 尾节点连接到第二个节点,形成环

        Solution sol = new Solution();
        System.out.println(sol.hasCycle(head)); // 输出 true,表示链表中存在环
    }
}
Python
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 定义快慢指针,并初始化为链表头节点
        slow = head
        fast = head

        # 使用快慢指针判断链表中是否存在环
        while fast and fast.next:
            slow = slow.next       # 慢指针每次移动一步
            fast = fast.next.next  # 快指针每次移动两步
            if slow == fast:       # 如果快慢指针相遇,说明存在环
                return True

        # 如果快指针到达链表尾部,说明不存在环
        return False

# 创建一个有环的链表
head = ListNode(3)
head.next = ListNode(2)
head.next.next = ListNode(0)
head.next.next.next = ListNode(-4)
head.next.next.next.next = head.next  # 尾节点连接到第二个节点,形成环

sol = Solution()
print(sol.hasCycle(head))  # 输出 True,表示链表中存在环

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/532179.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

day7 nest商业项目初探·三(java转ts全栈/3R教室)

背景&#xff1a;从头一点点学起太慢了&#xff0c;直接看几个商业项目吧&#xff0c;看看根据Java的经验&#xff0c;自己能看懂多少&#xff0c;然后再系统学的话也会更有针对性。今天看下一个项目 * 【法国 | 3.75w】Nextjs&#xff1a;小雯工作室创意官网 &#xff08;2023…

C语言进阶|顺序表

✈顺序表的概念及结构 线性表&#xff08;linear list&#xff09;是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构&#xff0c;常见的线性表&#xff1a;顺序表、链表、栈、队列、字符串.. 线性表在逻辑上是线性结构&#xff0c;也就说是连…

Proxmox VE qm 方式备份虚拟机

前言 使用qm 备份Proxmox VE虚拟机&#xff0c;高效便捷。 登录Proxmox VE shell 执行备份操作 备份建议关闭虚拟机 qm shutdown 虚拟机名称号--compress 备份格式 0(代表vma格式) gzip lzo zstd--storage local&#xff08;备份的位置&#xff09;备份默认位置/var/lib/…

NL2SQL基础系列(1):业界顶尖排行榜、权威测评数据集及LLM大模型(Spider vs BIRD)全面对比优劣分析[Text2SQL、Text2DSL]

NL2SQL基础系列(1)&#xff1a;业界顶尖排行榜、权威测评数据集及LLM大模型&#xff08;Spider vs BIRD&#xff09;全面对比优劣分析[Text2SQL、Text2DSL] Text-to-SQL&#xff08;或者Text2SQL&#xff09;&#xff0c;顾名思义就是把文本转化为SQL语言&#xff0c;更学术一…

【笔试】02

TCP TCP&#xff08;传输控制协议&#xff09;是一种面向连接的、可靠的、基于字节流的传输层通信协议 它能够提供以下服务&#xff1a; 可靠传输 通过序列号、确认应答、重传机制等确保数据完整、准确地从发送端传输到接收端。 三次握手&#xff1a; 点对点全双工面向字节流…

leetcode之35 搜索插入位置

文章目录 每日碎碎念一、题目要求及测试点35 搜索插入位置测试点提示 二、题解自己上手正经题解暴力法二分法之优化了一下逻辑 三、总结 每日碎碎念 苦痛生活继续 hello LeetCode&#xff0c;今天还是数组二分专项刷题… 一、题目要求及测试点 35 搜索插入位置 给定一个排序…

RecyclerView的使用

首先是activity_Main.xml 注意&#xff0c;少了下面那行活动页面会空白 app:layoutManager"androidx.recyclerview.widget.LinearLayoutManager" 1.然后需要创建一个java对象 public class NewsBean implements Serializable { // private String title;priva…

JR-SMD201-P便携式网络解码器

详细介绍&#xff1a; JR-SMD201-P便携式网络解码器采用1/2U设计&#xff0c;支持AVS/H.265/H.264/MPEG2解码&#xff0c;支持IP输入&#xff0c;支持1080P/1080I/720P/576I/480I多种分辨率&#xff0c;支持DRA/AC3/EAC3/AAC/MPEG等音频。 产品特点 支持输入方式IP 接口丰富&a…

Spring Boot 切面的一种的测试方法,java中级开发面试

void afterReturnName() { Assertions.assertEquals(studentController.getNameById(123L).getName(), "测试姓名Yz");} } 但往往切面中的逻辑并非这么简单&#xff0c;在实际的测试中其实我们也完成没有必要关心在切面中到底发生了什么&#xff08;发生了什么应该在…

Spring boot 入门 ---(一),2024年最新java进阶训练营

spring-snapshots http://repo.spring.io/snapshot spring-milestones http://repo.spring.io/milestone spring-boot-starter-parent是使用Spring Boot的一种不错的方式&#xff0c;但它 并不总是最合适的。有时你可能需要继承一个不同的父POM&#xff0c;或只是不喜欢我…

Kafka是什么,以及如何使用SpringBoot对接Kafka

系列文章目录 上手第一关&#xff0c;手把手教你安装kafka与可视化工具kafka-eagle 架构必备能力——kafka的选型对比及应用场景 Kafka存取原理与实现分析&#xff0c;打破面试难关 防止消息丢失与消息重复——Kafka可靠性分析及优化实践 Kafka是什么&#xff0c;以及如何使用…

Android输入框架

输入是一个操作系统的重要组成部分&#xff0c;没有输入&#xff0c;用户就无法向系统发送指令&#xff0c;也就没法完成人机交互。在Android系统中&#xff0c;输入系统是不可缺少的&#xff0c;下面简单介绍输入系统的整体框架&#xff0c;以下内容参考清华出版社出版的《And…

DSP笔记6-C2000的中断机制

中断Interrupt&#xff1a; 单核CPU顺序执行程序 中断源&#xff0c;引起计算机中断的时间&#xff0c;解放cpu&#xff0c;提高效率。 三个等级&#xff1a;CPU中断&#xff0c;PIE中断&#xff0c;外设中断 cpu定时器&#xff0c;EPWM&#xff0c;ADC&#xff0c;eCAP&…

计算机网友将饭卡余额改成100多万

你在学校干过最疯狂的事是什么&#xff1f; 一位学计算机的网友说&#xff0c;他改造过的水卡和饭卡都能无限使用&#xff0c;两年后在食堂刷卡&#xff0c;被食堂阿姨发现余额竟然还剩一百多万&#xff0c;虽然没有赔钱&#xff0c;但是被学校教务处处分了&#xff0c;怎么说…

03-JAVA设计模式-装饰模式

装饰模式 什么装饰模式 装饰器模式&#xff08;Decorator Pattern&#xff09;也叫包装器模式&#xff0c;是一种结构型设计模式&#xff0c;允许用户在不改变对象的情况下&#xff0c;动态地给对象增加一些额外的职责&#xff08;功能&#xff09;。装饰器模式相比生成子类更…

OSCP靶场--Hetemit

OSCP靶场–Hetemit 考点(python代码注入 systemctrl提权) 1.nmap扫描 ## ┌──(root㉿kali)-[~/Desktop] └─# nmap 192.168.173.117 -sV -sC -Pn --min-rate 2500 -p- Starting Nmap 7.92 ( https://nmap.org ) at 2024-04-10 05:52 EDT Nmap scan report for 192.168.1…

预训练的启蒙:浅谈BERT、RoBERTa、ALBERT、T5

文章目录 Transformer揭开预训练序幕为什么RNN/LSTM需要从头训练&#xff1f; BERT核心特点预训练任务架构应用和影响 RoBERTa改进点BERT和RoBERTa的MASK策略对比BERT的静态MASK策略RoBERTa的动态MASK策略效果 总结 ALBERT改进点参数共享因式分解嵌入参数和LoRa对比 总结 T5核心…

Chrome谷歌下载入口

​hello&#xff0c;我是小索奇 发现好多人说谷歌浏览器在哪里下载呀&#xff0c;哪里可以找到&#xff1f; 你可能会心想&#xff0c;一个浏览器你还不会下载啊&#xff1f; 还真是&#xff0c;有很多伙伴找不到下载入口&#xff0c;为什么呢&#xff1f; Bing进行搜索&am…

微信小程序转盘抽奖

场景&#xff1a; 在微信小程序里面开展抽奖活动使用转盘抽奖&#xff1b;类似下图&#xff08;图片来自百度&#xff09; 方法&#xff1a; 使用lukcy-canvas组件 在 微信小程序 中使用 | 基于 Js / TS / Vue / React / 微信小程序 / uni-app / Taro 的【大转盘 & 九宫…

unipush+个推实现消息推送

1.注册个推平台的帐号个推&#xff0c;专业的数据智能服务商-为垂直领域提供数据智能解决方案 2.应用列表中选择新增应用/服务 3.填写下应用信息4.创建好应用后在manifest.json中的sdkConfigs配置上写入appid、appkey、appsecret "sdkConfigs" : {"ad" :…