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

算法套路四——反转链表

算法套路四——反转链表

算法示例一:LeetCode206. 反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
初始化pre为空,cur为头指针

pre指针:记录当前结点的前一个结点
cur指针:记录当前结点,cur的next指针指向pre
nxt指针:记录当前结点的后一个结点,记录cur的next,防止断链
循环中左边按照ncpc的顺序反转,右边按照cpcn的顺序,且左右两边第一个c都为cur.next
在这里插入图片描述
反转结束后,从原来的链表上看:pre指向反转这一段的末尾,cur指向反转这一段后续的下一个节点

class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:pre = Nonecur = headwhile cur:nxt = cur.nextcur.next = prepre = curcur = nxt#顺序为ncpcreturn pre

算法示例二:LeetCode92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。
在这里插入图片描述

这题比前一题相比只是在中间进行反转,

  • 如果left=1,那么反转的逻辑与前一题一样,可以令pre = None,cur = head
  • 但若是left>1,我们在反转时不是从head开始,那么在反转后需要一个结点p0来记录反转的前一个结点,从而反转后可以连接到前面的结点

但分情况讨论在问题复杂时比较麻烦,所以我们可以用到反转链表时常用的哨兵dummy结点,它可以作为一个“假”的头结点,它的下一个结点指向真正的头结点head,这样的话就可以认为left无论是大于或是等于1,都可以用p0来记录反转前的结点

初始化后如图所示
pre指向null,p0指向反转前一个结点,
在这里插入图片描述

在反转结束后链表结构如下图所示:
在这里插入图片描述

因此直接令
p0.next.next=cur
p0.Next = pre
最后结果是
在这里插入图片描述
且最后返回dummy.next,不管head结点是否参与反转,dummy.next一定是指向反转后的链表头结点

func reverseBetween(head *ListNode, left int, right int) *ListNode {dummy := &ListNode{Val: 0, Next: head}p0:=dummyfor i:=1;i<left;i++{p0=p0.Next}var pre,cur *ListNode = nil, p0.Nextfor i:=0;i<right-left+1;i++{nxt:=cur.Nextcur.Next=prepre=curcur=nxt}p0.Next.Next = curp0.Next = prereturn dummy.Next
}

练习Leetcode25. K 个一组翻转链表

给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。在这里插入图片描述

此题首先按照上一题的思路,在第一次反转后如图所示
在这里插入图片描述
之后进行下一次反转时如果按照上题的思路对p0进行移动 p0.Next.Next = cur p0.Next = pre,会得到如下图示

在这里插入图片描述
我们可以发现在进行转变后,对3,4进行反转时丢失了反转前一个节点,这样会导致之后的反转丢失前链,所以我们在转变之前需要一个变量pnext来记录p0.next,从而可以记录第二次反转的前一个结点指针,然后进行p0.Next.Next = cur、p0.Next = pre赋值后,再将pnext赋给p0
最后如上题一样返回dummy.next

func reverseKGroup(head *ListNode, k int) *ListNode {n:=0for node:=head;node!=nil;node=node.Next{n++}dummy := &ListNode{Val: 0, Next: head}var pre *ListNode=nilcur:=headp0:=dummyfor ;n>=k;n-=k{for i:=0;i<k;i++{nxt:=cur.Nextcur.Next=prepre=curcur=nxt}p0.Next.Next = curpnext:=p0.Next//记录p0.Next,防止断链p0.Next = prep0=pnext}return dummy.Next
}

练习LeetCode24. 两两交换链表中的节点

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
在这里插入图片描述

相关文章:

算法套路四——反转链表

算法套路四——反转链表 算法示例一&#xff1a;LeetCode206. 反转链表 给你单链表的头节点 head &#xff0c;请你反转链表&#xff0c;并返回反转后的链表。 初始化pre为空&#xff0c;cur为头指针 pre指针&#xff1a;记录当前结点的前一个结点 cur指针&#xff1a;记录当…...

多线程 (六) wait和notify

&#x1f389;&#x1f389;&#x1f389;点进来你就是我的人了 博主主页&#xff1a;&#x1f648;&#x1f648;&#x1f648;戳一戳,欢迎大佬指点!人生格言&#xff1a;当你的才华撑不起你的野心的时候,你就应该静下心来学习! 欢迎志同道合的朋友一起加油喔&#x1f9be;&am…...

React--》状态管理工具—Mobx的讲解与使用

目录 Mobx的讲解与使用 Mobx环境配置 Mobx的基本使用 Mobx计算属性的使用 Mobx监听属性的使用 Mobx处理异步的使用 Mobx的模块化 Mobx的讲解与使用 Mobx是一个可以和React良好配合的集中状态管理工具&#xff0c;mobx和react的关系相当于vuex和vue之间的关系&#xff0…...

有效的括号长按键入验证外星语词典字符的最短距离用栈实现队列

有效的括号来源&#xff1a;杭哥20. 有效的括号 - 力扣&#xff08;LeetCode&#xff09;bool isValid(char * s) {int szstrlen(s);char stack[sz];int k0;for (int i0;i<sz;i){if (s[i]( || s[i][ || s[i]{){stack[k]s[i];}else{if (k0){return false;}else if (s[i]} &am…...

《前端开发者的进阶之路》

前端作为Web开发的重要领域之一&#xff0c;不断地发展和演变着。除了基本的HTML、CSS、JavaScript技能&#xff0c;前端开发者需要掌握更多的进阶知识才能应对不断变化的需求。本文将介绍一些前端的进阶知识&#xff0c;帮助前端开发者进一步提高自己的技能水平。1.框架和库在…...

为什么说网络安全是风口行业?是IT行业最后的红利?

前言 “没有网络安全就没有国家安全”。当前&#xff0c;网络安全已被提升到国家战略的高度&#xff0c;成为影响国家安全、社会稳定至关重要的因素之一。 网络安全行业特点 1、就业薪资非常高&#xff0c;涨薪快 2021年猎聘网发布网络安全行业就业薪资行业最高人均33.77万&…...

使用shell 脚本,批量解压一批zip文件,解压后的文件放在以原zip文件名前10个字符的文件夹中的例子

#!/bin/bash for file in *.zip dofolder$(echo $file | cut -c 1-10)mkdir $folderunzip -q $file -d $folder doneecho "All zip files have been extracted." # 说明&#xff1a; # 1. for循环遍历当前目录下的所有zip文件 # 2. 使用cut命令提取zip文件名前10个字…...

01 | Msyql系统架构

目录MySQL系统架构连接器查询缓存分析器优化器执行器MySQL系统架构 大体来说&#xff0c;MySQL分为Server层和引擎层两部分。 Server层包含链接器、查询缓存、分析器、优化器和执行器&#xff0c;而引擎层负责的是数据的存储和读取&#xff0c;支持InnoDB、Myisam、Memory等多…...

Linux命令---设备管理

Linux setleds命令Linux setleds命令用来设定键盘上方三个 LED 的状态。在 Linux 中&#xff0c;每一个虚拟主控台都有独立的设定。语法setleds [-v] [-L] [-D] [-F] [{|-}num] [{|-}caps] [{|-}scroll]参数&#xff1a;-F&#xff1a;预设的选项&#xff0c;设定虚拟主控台的状…...

前端入门:HTML5+CSS3+JAAVASCRIPT

1、 初识HTML HTML:Hyper Text Markup Language(超文本标记语言) 。 超文本包括&#xff1a;文字、图片、音频、视频、动画等。 1.1、W3C标准 1.2、HTML基本结构 示例&#xff1a; <!-- DOCTYPE:告诉浏览器&#xff0c;我们要使用什么规划&#xff0c;这里是HTML --> …...

【头歌实验】课外作业一:开通ECS及使用Linux命令

文章目录一、完成下列实验并截图二、简要回答“课堂考核”内容三、在头歌、华为云或阿里云官网上&#xff0c;找出自己的课外学习资源&#xff0c;制定小组的课程学习计划、专业学习计划。四、习题1.10一、完成下列实验并截图 1、实验《ECS云服务器新手上路》 https://develo…...

CMSIS-RTOS2 RTX5移植到GD32L233

1、CMSIS-RTOS2是什么&#xff1f; 关于CMSIS-RTOS2的官方描述如下&#xff1a; CMSIS-RTOS v2 &#xff08;CMSIS-RTOS2&#xff09; 为基于 Arm Cortex 处理器的设备提供通用 RTOS 接口。它为需要RTOS功能的软件组件提供了一个标准化的API&#xff0c;因此为用户和软件行业带…...

[网络原理] 网络中的基本概念

人生,本就是苦乐参半,这样的生活才是丰富多彩. 文章目录前言1. IP地址2. 端口号3. 协议4. 五元组5. 协议分层6. OSI七层模型7. TCP/IP协议8. 封装和分用9. 客户端与服务端10. 请求与响应前言 本章开始,我们开启网络部分的知识大门. 1. IP地址 1.定义: IP地址主要用于表示网络…...

BeanPostProcessor原理分析

文章目录一、BeanPostProcessor的作用1. 源码2. 使用案例二、Spring生命周期中的BeanPostProcessor三、BeanPostProcessor对PostConstruct的支持四、BeanPostProcessor中的顺序性五、总结一、BeanPostProcessor的作用 BeanPostProcessor提供了初始化前后回调的方法&#xff0c;…...

人工智能和网络安全,应该如何选择?

随着数字时代的到来&#xff0c;网络安全和人工智能成了科技创新产业的重要组成部分。也逐渐成了大多数人心中热门的行业选择。那么该如何抉择呢&#xff1f; 首先我们来了解下人工智能的发展前景&#xff1a; ​ 如今&#xff0c;人工智能技术无论是在核心技术方面&#xff0…...

Flink预加载分区维表,实时更新配置信息

当前我们的业务场景&#xff0c;是基于dataStream代码&#xff0c; 维表数据量很大&#xff0c; 实时性要求很高&#xff0c;所以采用预加载分区维表模式&#xff0c; kafka广播流实时更新配置。 实现方案 1&#xff1a;job初始化时 每个分区open 只加载自己那部分的配置&…...

大数据现在找工作难么

大数据行业工作好找还是难找不是光靠嘴说出来的结合实际&#xff0c;看看市场上的招聘需求和岗位要求就大致知道了 要想符合企业用人规范&#xff0c;学历&#xff0c;工作经验&#xff0c;掌握技能都是非常重要的~ 先来看几个招聘网站的报告数据&#xff1a; Boss直聘发布的…...

【Linux】学会这些基本指令来上手Linux吧

前言上篇文章介绍了一些常用的指令&#xff0c;这篇文章再来介绍一下Linux必须学会的指令。一.时间相关的指令ate显示date 指定格式显示时间&#xff1a; date %Y:%m:%d date 用法&#xff1a;date [OPTION]... [FORMAT]1.在显示方面&#xff0c;使用者可以设定欲显示的格式&am…...

【沐风老师】3DMAX交通流插件TrafficFlow使用方法详解

TrafficFlow交通流插件&#xff0c;模拟生成车流、人流动画。 【版本要求】 3dMax 2008及更高版本 【安装方法】 无需安装直接拖动插件脚本文件到3dMax视口中打开。 【快速开始】 1.创建车辆对象和行车路径。 2.打开TrafficFlow插件&#xff0c;先选择“车辆”对象&#xff0…...

c#实现视频的批量剪辑

篇首&#xff0c;完全没有技术含量的帖子&#xff0c;高手略过&#xff0c;只为十几年后重新捡起的我爱好玩玩。。。 起因&#xff0c;一个朋友说他下载了很多短视频&#xff0c;但只需要要其中的一小截&#xff0c;去头掐尾&#xff0c;在软件里搞来搞去太麻烦&#xff0c;让…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

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

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

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...