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

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...