当前位置: 首页 > news >正文

备战蓝桥杯—— 双指针技巧巧答链表1

        对于单链表相关的问题,双指针技巧是一种非常广泛且有效的解决方法。以下是一些常见问题以及使用双指针技巧解决:

  1. 合并两个有序链表: 使用两个指针分别指向两个链表的头部,逐一比较节点的值,将较小的节点链接到结果链表中,直至其中一个链表遍历完毕。

  2. 链表的分解: 使用快慢指针技巧,快指针每次移动两步,慢指针每次移动一步,直到快指针到达链表尾部。这样可以找到链表的中间节点,从而将链表分解成两部分。

  3. 合并 k 个有序链表: 可以利用归并排序的思想,两两合并链表,直到合并成一个链表。

  4. 寻找单链表的倒数第 k 个节点: 使用两个指针,让一个指针先移动 k 步,然后两个指针一起移动,直到第一个指针到达链表尾部,此时第二个指针指向的节点即为倒数第 k 个节点。

  5. 寻找单链表的中点: 同样使用快慢指针技巧,快指针每次移动两步,慢指针每次移动一步,直到快指针到达链表尾部,慢指针即为中点。

  6. 判断单链表是否包含环并找出环起点: 使用快慢指针技巧,如果存在环,快指针最终会追上慢指针。找到相遇点后,将其中一个指针移动到链表头部,然后两个指针以相同速度移动,再次相遇的节点即为环的起点。

  7. 判断两个单链表是否相交并找出交点: 分别遍历两个链表,得到它们的长度差,然后让长链表的指针先移动长度差步数,接着两个链表同时遍历,直到找到相同的节点为止。

总的来说,双指针技巧在解决单链表相关问题时非常实用,它能够高效地解决许多常见问题,包括合并、分解、寻找节点、判断是否存在环等等。而我们需要使用双指针解决的以上问题,则是先要学会以下问题的解题思路,一起看看。

一、环形链表

题目描述

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

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

解题思路及代码

         利用快慢指针原理 一个指针走得快,另一个走得慢,如果有循环,快指针会在莫个时刻追上慢的指针

/** 自定义类** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {//判断是否有循环public boolean hasCycle(ListNode head) {//判断是否为空指针   解决特殊情况if(head==null)return false;//定义另一个指针ListNode second=head.next;//利用快慢指针原理 一个指针走得快,另一个走得慢,如果有循环,//快指针会在莫个时刻追上慢的指针while(head!=null && second!=null && second.next!=null){head=head.next;second=second.next.next;//如果快指针追上慢指针,说明有循环if(head==second){return true;}}//如果两个指针同时为空,说明没有循环return false;}
}

运行结果

二、环形链表||

题目描述

        给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

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

不允许修改 链表。

示例 1:

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

示例 2:

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

示例 3:

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

解题思路及代码

         如果有环,快指针走的距离是慢指针的两倍,设总距离为2x。快指针首次在链表尾连接到链表中的位置移动了2x,慢指针移动了x。快指针追上慢指针,快指针走的距离为2x+2/3k环;慢指针的距离为 x+1/3k环。设置起点到链表尾连接到链表中的位置距离为l,现在慢指针再跟快指针按同样的速度行走l,两指针就可以在链表尾连接到链表中的位置相遇。

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {//声明快慢指针ListNode second=head;ListNode first=head;//判断是否有环while(second!=null && second.next!=null){first=first.next;second=second.next.next;if(first==second){break;}}//如果没有环,直接返回nullif(second==null || second.next==null){return null;}//如果有环,快指针走的距离是慢指针的两倍,设总距离为2x。快指针首次在链表尾连接到链表中的位置移动了2x,慢指针移动了x。快指针追上慢指针,快指针走的距离为2x+2/3k环;慢指针的距离为 x+1/3k环。设置起点到链表尾连接到链表中的位置距离为l,现在慢指针再跟快指针按同样的速度行走l,两指针就可以在链表尾连接到链表中的位置相遇。first=head;while(first!=second){first=first.next;second=second.next;}return first;}
}

运行结果

相关文章:

备战蓝桥杯—— 双指针技巧巧答链表1

对于单链表相关的问题&#xff0c;双指针技巧是一种非常广泛且有效的解决方法。以下是一些常见问题以及使用双指针技巧解决&#xff1a; 合并两个有序链表&#xff1a; 使用两个指针分别指向两个链表的头部&#xff0c;逐一比较节点的值&#xff0c;将较小的节点链接到结果链表…...

微信小程序返回上一级页面并自动刷新数据

文章目录 前言一、获取小程序栈二、生命周期触发总结 前言 界面由A到B&#xff0c;在由B返回A&#xff0c;触发刷新动作 一、获取小程序栈 界面A代码 shuaxin(){//此处可进行接口请求从而实现更新数据的效果console.log("刷新本页面数据啦")},界面B代码 // 返回触…...

Spring⼯⼚创建复杂对象

文章目录 5. Spring⼯⼚创建复杂对象5.1 什么是复杂对象5.2 Spring⼯⼚创建复杂对象的3种⽅式5.2.1 FactoryBean 接口5.2.2 实例⼯⼚5.2.3 静态工厂 5.3 Spring 工厂的总结 6. 控制Spring⼯⼚创建对象的次数6.1 如何控制简单对象的创建次数6.2 如何控制复杂对象的创建次数6.3 为…...

Top-N 泛型工具类

一、代码实现 通过封装 PriorityQueue 实现&#xff0c;PriorityQueue 本质上是完全二叉树实现的小根堆&#xff08;相对来说&#xff0c;如果比较器反向比较则是大根堆&#xff09;。 public class TopNUtil<E extends Comparable<E>> {private final PriorityQ…...

Java 后端面试指南

面试指南 TMD&#xff0c;一个后端为什么要了解那么多的知识&#xff0c;真是服了。啥啥都得了解 MySQL MySQL索引可能在以下几种情况下失效&#xff1a; 不遵循最左匹配原则&#xff1a;在联合索引中&#xff0c;如果没有使用索引的最左前缀&#xff0c;即查询条件中没有包含…...

142.环形链表 ||

给定一个链表的头节点 head &#xff0c;返回链表开始入环的第一个节点。 如果链表无环&#xff0c;则返回 null。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中存在环。 为了表示给定链表中的环&#xff0c;评测系统内部使用整…...

Nacos、Eureka、Zookeeper注册中心的区别

Nacos、Eureka和Zookeeper都是常用的注册中心&#xff0c;它们在功能和实现方式上存在一些不同。 Nacos除了作为注册中心外&#xff0c;还提供了配置管理、服务发现和事件通知等功能。Nacos默认情况下采用AP架构保证服务可用性&#xff0c;CP架构底层采用Raft协议保证数据的一…...

CSS重点知识整理1

目录 1 平面位移 1.1 基本使用 1.2 单独方向的位移 1.3 使用平面位移实现绝对位置居中 2 平面旋转 2.1 基本使用 2.2 圆点转换 2.3 多重转换 3 平面缩放 3.1 基本使用 3.2 渐变的使用 4 空间转换 4.1 空间位移 4.1.1 基本使用 4.1.2 透视 4.2 空间旋转 4.3 立…...

【Langchain多Agent实践】一个有推销功能的旅游聊天机器人

【LangchainStreamlit】旅游聊天机器人_langchain streamlit-CSDN博客 视频讲解地址&#xff1a;【Langchain Agent】带推销功能的旅游聊天机器人_哔哩哔哩_bilibili 体验地址&#xff1a; http://101.33.225.241:8503/ github地址&#xff1a;GitHub - jerry1900/langcha…...

算法学习(十二)并查集

并查集 1. 概念 并查集主要用于解决一些 元素分组 问题&#xff0c;通过以下操作管理一系列不相交的集合&#xff1a; 合并&#xff08;Union&#xff09;&#xff1a;把两个不相交的集合合并成一个集合 查询&#xff08;Find&#xff09;&#xff1a;查询两个元素是否在同一…...

TensorRT及CUDA自学笔记003 NVCC及其命令行参数

TensorRT及CUDA自学笔记003 NVCC及其命令行参数 各位大佬&#xff0c;这是我的自学笔记&#xff0c;如有错误请指正&#xff0c;也欢迎在评论区学习交流&#xff0c;谢谢&#xff01; NVCC是一种编译器&#xff0c;基于一些命令行参数可以将使用PTX或C语言编写的代码编译成可…...

数据库管理-第154期 Oracle Vector DB AI-06(20240223)

数据库管理154期 2024-02-23 数据库管理-第154期 Oracle Vector DB & AI-06&#xff08;20240223&#xff09;1 环境准备创建表空间及用户TNSNAME配置 2 Oracle Vector的DML操作创建示例表插入基础数据DML操作UPDATE操作DELETE操作 3 多Vector列表4 固定维度的向量操作5 不…...

解决uni-app vue3 nvue中使用pinia页面空白问题

main.js中&#xff0c;最关键的就是Pinia要return出去的问题&#xff0c;至于原因嘛! 很忙啊&#xff0c;先用着吧 import App from ./App import * as Pinia from pinia import { createSSRApp } from vue export function createApp() {const app createSSRApp(App);app.us…...

不用加减乘除做加法

1.题目&#xff1a; 写一个函数&#xff0c;求两个整数之和&#xff0c;要求在函数体内不得使用、-、*、/四则运算符号。 数据范围&#xff1a;两个数都满足 −10≤&#xfffd;≤1000−10≤n≤1000 进阶&#xff1a;空间复杂度 &#xfffd;(1)O(1)&#xff0c;时间复杂度 &am…...

旅游组团自驾游拼团系统 微信小程序python+java+node.js+php

随着社会的发展&#xff0c;旅游业已成为全球经济中发展势头最强劲和规模最大的产业之一。为方便驴友出行&#xff0c;寻找旅游伙伴&#xff0c;更好的规划旅游计划&#xff0c;开发一款自驾游拼团小程序&#xff0c;通过微信小程序发起自驾游拼团&#xff0c;吸收有车或无车驴…...

LeetCode 第41天 | 背包问题 二维数组 一维数组 416.分割等和子集 动态规划

46. 携带研究材料&#xff08;第六期模拟笔试&#xff09; 题目描述 小明是一位科学家&#xff0c;他需要参加一场重要的国际科学大会&#xff0c;以展示自己的最新研究成果。他需要带一些研究材料&#xff0c;但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实…...

Ubuntu20.04和Windows11下配置StarCraft II环境

1.Ubuntu20.04 根据下面这篇博客就可以顺利安装&#xff1a; 强化学习实战(九) Linux下配置星际争霸Ⅱ环境https://blog.csdn.net/weixin_39059031/article/details/117247635?spm1001.2014.3001.5506 Ubuntu下显示游戏界面目前还没有解决掉。 大家可以根据以下链接看看能…...

【NCom】:通过高温气相合成调节Pt-CeO2相互作用以提高晶格氧的还原性

摘要&#xff1a;在这项工作中&#xff0c;我们比较了通过两种方法制备的 Pt 单原子催化剂&#xff08;SAC&#xff09;的 CO 氧化性能&#xff1a;&#xff08;1&#xff09;传统的湿化学合成&#xff08;强静电吸附strong electrostatic adsorption–SEA&#xff09;&#xf…...

git 将一个分支的提交移动到另一个分支

假设想把分支A上的最后一部分commit移动到分支B之上&#xff1a; 首先切到分支B git checkout B然后执行如下指令,commit id 为A分支上&#xff0c;需要移动的那些提交 git cherry-pick <commit id> &#xff08; <commit id> 可多个&#xff09;中途可能遇到一些…...

vue3 实现 el-pagination页面分页组件的封装以及调用

示例图 一、组件代码 <template><el-config-provider :locale"zhCn"><el-pagination background class"lj-paging" layout"prev, pager, next, jumper" :pager-count"5" :total"total":current-page"p…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...