当前位置: 首页 > 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…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...

Xela矩阵三轴触觉传感器的工作原理解析与应用场景

Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知&#xff0c;帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量&#xff0c;能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度&#xff0c;还为机器人、医疗设备和制造业的智…...