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

数据结构:链表的双指针技巧

文章目录

      • 一、链表相交问题
      • 二、单链表判环问题
      • 三、回文链表
      • 四、重排链表结点

初学双指针的同学,请先弄懂删除链表的倒数第 N 个结点。
并且在学习这一节时,不要将思维固化,认为只能这样做,这里的做法只是技巧。

一、链表相交问题

LeetCode:160.相交链表
  题目要求时间复杂度为O(L1+L2),空间复杂度为O(1),实际上并不是说只能遍历一次,单个链表遍历常数次,时间复杂度仍为O(L)。我们可以采用如下方法解决:

  1. 计算两个链表的长度:首先遍历两个链表,计算它们各自的长度(lenAlenB),同时检查链表的末尾节点是否相同。如果末尾节点不同,则两个链表不相交,直接返回NULL。这一步也确保了,如果两个链表相交,它们的末尾节点必定是相同的。(对于存在相交的链表,它们的的末尾结点一定是一样的!

  2. 调整起点:为了同步遍历两个链表找到交点,需要从两个链表相同的“距离”开始遍历。由于两个链表可能长度不同,我们先计算长度差abs(lenA-lenB)。然后让较长的链表的指针先前进这个长度差的步数。这样做的目的是让两个链表的指针能够在同一起跑线上“开始比赛”。

  3. 同步前进直到找到交点:之后,同时前进两个链表的指针,直到它们相遇。由于步骤2已经确保了两个指针距离链表末尾的距离相同,所以它们会在交点相遇。如果两个链表有交点,那么这个交点是两个指针第一次相遇的地方。

这段代码的关键在于通过计算长度差并同步前进两个指针来找到可能的交点。这种方法不需要修改链表结构,也不需要额外的存储空间,效率较高。在最坏的情况下,时间复杂度是O(L1+L2),其中L1和L2分别是两个链表的长度。

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {//if(!headA||!headB) return NULL;int lenA=0,lenB=0;ListNode * travelA=headA,* travelB=headB;while(travelA->next||travelB->next){if(travelA->next) {travelA=travelA->next;++lenA;}if(travelB->next) {travelB=travelB->next;++lenB;}}if(travelA!=travelB) return NULL;if(lenB>lenA) swap(headA,headB);lenA=abs(lenA-lenB);//复用for(int i=0;i<lenA;++i) headA=headA->next;while(headA!=headB){headA=headA->next;headB=headB->next;}return headA;}
};


防止大脑已经不会暴力,暴力解法:
①对于L1,从头遍历L1的每一个结点,判断该结点是否在L2中,如果在,则是相交结点。(从头遍历,第一个在的是相交结点),如果每次都遍历一次L2,则时间复杂度O(L1*L2)
②无脑的哈希优化,将L2的结点存入一个哈希表(集合),每次判断时只平均需要O(1)的时间,所以时间复杂度为O(L1+L2),空间复杂度O(L2)。

哈希优化:

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {//if(!headA||!headB) return NULL;unordered_set<ListNode * > Set;while(headA){Set.insert(headA);headA=headA->next;}while(headB){if(Set.count(headB)) return headB;headB=headB->next;}return NULL;}
};

二、单链表判环问题

LeetCode:141.环型链表
  题目要求使用空间复杂度为O(1),因此不能用哈希解决,用哈希只需要遍历的过程中将结点存入哈希表,每次遍历先判断该结点是否在哈希表中,如果不在则存入哈希表,如果在则找到环。但是哈希表的空间复杂度为O(L),因此我们只能用其他方法。
  这里使用双指针,一个慢指针slow,一个快指针fastslow一次走一步,fast一次走两步。类似于跑步比赛,从同一个长道出发,跑向运动场的跑道上跑步,由于快指针跑的速度是慢指针的两倍,快指针总会多跑一圈然后超过慢指针。
  因此如果只需要判断是否存在环只需要这样做,无环的话fast一定先跑到底:

class Solution {
public:bool hasCycle(ListNode *head) {if(!head||!head->next) return false;ListNode * slow=head;ListNode * fast=head;while(fast!=nullptr && fast->next!=nullptr){slow=slow->next;fast=fast->next->next;if(fast==slow) return true;}return false;}
};

不过,我们知道在行走时,还有信息我们没有用到,我们是否能利用这些信息找到环的入口呢?信息:

  • 慢指针走的步数:step_slow,快指针走的步数:step_fast,则有step_fast=step_slow*2
  • 假设环外结点数为a,环中结点数为b,设x是fast和slow相遇时离换入口的距离,则step_fast=a+nb+x,step_slow=a+cb+x,(0<=x<b)。
  • 联立可得①a+nb+x=2a+2x+2cb②nb=a+x+2cb③(n-2c)b=a+x。
  • 由③可知a+x>0,且a+x是圈中结点数的倍数,换句话说,由于现在走到的位置是x,则在fastslow相遇的位置,再走a步可以走到环的入口(因为再走这么多步刚好是环的倍数步),换句话说,如果现在有一个指针p从环外起点出发,每次走一步,与fast或slow一同行走,走完环外结点个数步(a步)之后会在环的入口处相遇!

寻找环的入口

ListNode *detectCycle(ListNode *head) {ListNode *slow = head, *fast = head;// 第一次遍历,找到快慢指针相遇点while (fast != nullptr && fast->next != nullptr) {slow = slow->next;fast = fast->next->next;if (slow == fast) { // 发现环// 将其中一个指针(这里选择slow)移回头节点slow = head;// 两个指针以相同速度移动,再次相遇点即为环入口while (slow != fast) {slow = slow->next;fast = fast->next;}return slow; // 返回环入口}}return nullptr; // 无环
}

三、回文链表

LeetCode:234.回文链表
  回文链表,我们可以这样做,我们单独存一个原链表的反置之后的链表,然后反置的 和 原链表 从首位置开始齐步向前就行。(当然逆序的话,使用栈也是可以的!栈就相当于你存进去的东西想逆着拿出来,换句话说,你只需要逆序来查看某个东西的元素,存入栈是很好的选择!)不过时间复杂度需要的是O(1),我们需要一点点技巧。但是单链表怎么也不可能反着遍历呀!怎么办呢?!
在这里插入图片描述
将中点之后的链表部分翻转吧朋友:找到链表中点,然后将后面的链表翻转,然后就可以首尾齐进了。翻转链表只需要O(1)的时间复杂度,三个指针~,不过如果原题说不允许修改原结构,那就再翻转过了即可(虽然输入和输出只是一个接口,但是这确实只能说很离谱)。

反转链表的后半部分

  1. 找到中点:使用快慢指针找到链表的中间节点。
  2. 反转后半部分:从中间节点开始反转链表的后半部分。
  3. 比较前后半部分:将前半部分和反转后的后半部分进行比较,如果每个节点的值都相同,则链表是回文。
  4. 恢复链表(可选):如果需要保持原链表的结构,可以再次反转后半部分以恢复原链表。

这种方法的空间复杂度为O(1),但需要改变链表结构(如果不恢复的话)。

class Solution {
public:bool isPalindrome(ListNode* head) {if (head == nullptr) {return true;}// 找到前半部分链表的尾节点并反转后半部分链表ListNode* firstHalfEnd = endOfFirstHalf(head);ListNode* secondHalfStart = reverseList(firstHalfEnd->next);// 判断是否回文ListNode* p1 = head;ListNode* p2 = secondHalfStart;bool result = true;while (result && p2 != nullptr) {if (p1->val != p2->val) {result = false;}p1 = p1->next;p2 = p2->next;}        // 还原链表并返回结果firstHalfEnd->next = reverseList(secondHalfStart);return result;}ListNode* reverseList(ListNode* head) {ListNode* prev = nullptr;ListNode* curr = head;while (curr != nullptr) {ListNode* nextTemp = curr->next;curr->next = prev;prev = curr;curr = nextTemp;}return prev;}ListNode* endOfFirstHalf(ListNode* head) {ListNode* fast = head;ListNode* slow = head;while (fast->next != nullptr && fast->next->next != nullptr) {fast = fast->next->next;slow = slow->next;}return slow;}
};

四、重排链表结点

在这里插入图片描述
这个和回文链表是一样的,将中点之后的链表部分翻转,然后就可以一个一个选了。

相关文章:

数据结构:链表的双指针技巧

文章目录 一、链表相交问题二、单链表判环问题三、回文链表四、重排链表结点 初学双指针的同学&#xff0c;请先弄懂删除链表的倒数第 N 个结点。 并且在学习这一节时&#xff0c;不要将思维固化&#xff0c;认为只能这样做&#xff0c;这里的做法只是技巧。 一、链表相交问题 …...

用WHERE命令可以在命令行搜索文件

文章目录 用WHERE命令可以在命令行搜索文件概述笔记没用的小程序END 用WHERE命令可以在命令行搜索文件 概述 想确认PATH变量中是否存在某个指定的程序(具体是在PATH环境变量中给出的哪个路径底下?). 开始不知道windows有where这个命令, 还自己花了2个小时写了一个小程序. 后…...

持续交付/持续部署流水线介绍(CD)

目录 一、概述 二、典型操作流程 2.1 CI/CD典型操作流 2.2 CI/CD操作流程说明 2.3 总结 三、基于GitHubDocker的持续交付/持续部署流水线&#xff08;公有云&#xff09; 3.1 基于GitHubDocker的持续交付/持续部署操作流程示意图 3.2 GitHubDocker持续交付/持续部署流水…...

第四百三十八回

文章目录 1. 概念介绍2. 思路与方法2.1 实现思路2.2 实现方法 3. 示例代码4. 内容总结 们在上一章回中介绍了"不同平台上换行的问题"相关的内容&#xff0c;本章回中将介绍如何在页面上显示蒙板层.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1. 概念介绍 我们…...

Python学习:面相对象

面向对象 面向对象技术简介 类(Class): 用来描述具有相同的属性和方法的对象的集合。它定义了该集合中每个对象所共有的属性和方法。对象是类的实例。方法:类中定义的函数。类变量:类变量在整个实例化的对象中是公用的。类变量定义在类中且在函数体之外。类变量通常不作为实…...

SSM学习——Spring AOP与AspectJ

Spring AOP与AspectJ 概念 AOP的全称为Aspect-Oriented Programming&#xff0c;即面向切面编程。 想象你是汉堡店的厨师&#xff0c;每一份汉堡都有好几层&#xff0c;这每一层都可以视作一个切面。现在有一位顾客想要品尝到不同风味肉馅的汉堡&#xff0c;如果按照传统的方…...

Android 使用LeakCanary检测内存泄漏,分析原因

内存泄漏是指无用对象&#xff08;不再使用的对象&#xff09;持续占有内存或无用对象的内存得不到及时释放&#xff0c;从而造成内存空间的浪费称为内存泄漏。 平时我们在使用app时&#xff0c;少量的内存泄漏我们是发现不了的&#xff0c;但是当内存泄漏达到一定数量时&…...

Linux部署Kafka2.8.1

安装Jdk 首先确保你的机器上安装了Jdk&#xff0c;Kafka需要Java运行环境&#xff0c;低版本的Kafka还需要Zookeeper&#xff0c;我此次要安装的Kafka版本为2.8.1&#xff0c;已经内置了一个Zookeeper环境&#xff0c;所以我们可以不部署Zookeeper直接使用。 1、解压Jdk包 t…...

【pytest、playwright】allure报告生成视频和图片

目录 1、修改插件pytest_playwright 2、conftest.py配置 3、修改pytest.ini文件 4、运行case 5、注意事项 1、修改插件pytest_playwright pytest_playwright.py内容如下&#xff1a; # Copyright (c) Microsoft Corporation. # # Licensed under the Apache License, Ver…...

浅谈iOS开发中的自动引用计数ARC

1.ARC是什么 我们知道&#xff0c;在C语言中&#xff0c;创建对象时必须手动分配和释放适量的内存。然而&#xff0c;在 Swift 中&#xff0c;当不再需要类实例时&#xff0c;ARC 会自动释放这些实例的内存。 Swift 使用 ARC 来跟踪和管理应用程序的内存&#xff0c;其主要是由…...

Spring IoCDI(2)

IoC详解 通过上面的案例, 我们已经知道了IoC和DI的基本操作, 接下来我们来系统地学习Spring IoC和DI的操作. 前面我们提到的IoC控制反转, 就是将对象的控制权交给Spring的IoC容器, 由IoC容器创建及管理对象. (也就是Bean的存储). Bean的存储 我们之前只讲到了Component注解…...

30. UE5 RPG GamplayAbility的配置项

在上一篇文章&#xff0c;我们介绍了如何将GA应用到角色身上的&#xff0c;接下来这篇文章&#xff0c;将主要介绍一下GA的相关配置项。 在这之前&#xff0c;再多一嘴&#xff0c;你要能激活技能&#xff0c;首先要先应用到ASC上面&#xff0c;才能够被激活。 标签 之前介绍…...

提升自己最快的方式是什么?

提升自己最快的方式通常涉及到个人成长的各个方面&#xff0c;包括心理、情感、技能和知识等。根据查阅到的资料&#xff0c;以下是一些具体的方法和步骤&#xff0c;帮助你快速提升自己&#xff1a; 1. 培养屏蔽力 荷兰畅销书作家罗伊马丁纳提到&#xff0c;屏蔽力是个人成长…...

题目:一个5位数,判断它是不是回文数。即12321是回文数,个位与万位相同,十位与千位相同。

题目&#xff1a;一个5位数&#xff0c;判断它是不是回文数。即12321是回文数&#xff0c;个位与万位相同&#xff0c;十位与千位相同。    There is no nutrition in the blog content. After reading it, you will not only suffer from malnutrition, but also impotence…...

《HelloGitHub》第 96 期

兴趣是最好的老师&#xff0c;HelloGitHub 让你对编程感兴趣&#xff01; 简介 HelloGitHub 分享 GitHub 上有趣、入门级的开源项目。 https://github.com/521xueweihan/HelloGitHub 这里有实战项目、入门教程、黑科技、开源书籍、大厂开源项目等&#xff0c;涵盖多种编程语言 …...

C++tuple类型

tuple 类型 tuple是类似pair的模板。 每个pair的成员类型都不相同&#xff0c;但每个pair都恰好有两个成员。不同tuple类型的成员类型也不相同&#xff0c;但一个tuple可以有任意数量的成员。 每个确定的tuple类型的成员数目是固定的&#xff0c;但一个tuple类型的成员数目可…...

亚远景科技-浅谈ASPICE标准和ASPICE认证/评估

ASPICE&#xff08;Automotive SPICE&#xff09;是一种针对汽车行业的软件开发过程的评估模型&#xff0c;它旨在帮助汽车制造商和供应商提高软件开发过程的能力和质量&#xff0c;从而提升产品的质量、安全性和效率。 ASPICE标准涵盖了软件开发的各个阶段和活动&#xff0c;…...

PHP性能提升方案

一、背景与介绍 PHP语言开发效率高&#xff0c;特别应用于适合中小型项目&#xff0c;对于创业初期敏捷开发验证项目可行性或者Demo演示绝对占据优势。 但是随着现在Web应用的复杂性&#xff0c;针对项目要适应高并发、高流量的访问特性&#xff0c;PHP确实在性能方面相对Go、J…...

关系(二)利用python绘制热图

关系&#xff08;二&#xff09;利用python绘制热图 热图 &#xff08;Heatmap&#xff09;简介 热图适用于显示多个变量之间的差异&#xff0c;通过颜色判断彼此之间是否存在相关性。 快速绘制 基于seaborn import seaborn as sns import pandas as pd import numpy as np i…...

P8597 [蓝桥杯 2013 省 B] 翻硬币

# [蓝桥杯 2013 省 B] 翻硬币 ## 题目背景 小明正在玩一个“翻硬币”的游戏。 ## 题目描述 桌上放着排成一排的若干硬币。我们用 * 表示正面&#xff0c;用 o 表示反面&#xff08;是小写字母&#xff0c;不是零&#xff09;&#xff0c;比如可能情形是 **oo***oooo&#x…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...

客户案例 | 短视频点播企业海外视频加速与成本优化:MediaPackage+Cloudfront 技术重构实践

01技术背景与业务挑战 某短视频点播企业深耕国内用户市场&#xff0c;但其后台应用系统部署于东南亚印尼 IDC 机房。 随着业务规模扩大&#xff0c;传统架构已较难满足当前企业发展的需求&#xff0c;企业面临着三重挑战&#xff1a; ① 业务&#xff1a;国内用户访问海外服…...