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

【数据结构和算法】反转链表

其他系列文章导航

Java基础合集
数据结构与算法合集

设计模式合集

多线程合集

分布式合集

ES合集


文章目录

其他系列文章导航

文章目录

前言

一、题目描述

二、题解

2.1 方法一:迭代(双指针)

2.2 方法二:递归

三、代码

3.1 方法一:迭代(双指针)

3.2 方法二:递归

四、复杂度分析

4.1 方法一:迭代(双指针)

4.2 方法二:递归


前言

这是力扣的 206 题,难度为简单,解题方案有很多种,本文讲解我认为最奇妙的一种。

继续开始链表的模块了,这道题是一道非常好的队列的例题,很有代表性。


一、题目描述

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例 2:

输入:head = [1,2]
输出:[2,1]

示例 3:

输入:head = []
输出:[]

提示:

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?


二、题解

因为进阶要求两种方法来解决这道题目,所以本文都讲解!

如下图所示,题目要求将链表反转。本文介绍迭代(双指针)、递归两种实现方法。

Picture1.png

2.1 方法一:迭代(双指针)

思路与算法:

假设链表为 1→2→3→∅,我们想要把它改成 ∅←1←2←3。

在遍历链表时,将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点,因此必须事先存储其前一个节点。在更改引用之前,还需要存储后一个节点。最后返回新的头引用。

2.2 方法二:递归

递归版本稍微复杂一些,其关键在于反向工作。假设链表的其余部分已经被反转,现在应该如何反转它前面的部分?

假设链表为:
n1→…→nk−1→nk→nk+1→…→nm→∅

若从节点 nk+1到 nm已经被反转,而我们正处于 nk。

n1→…→nk−1→nk→nk+1←…←nm

我们希望 nk+1的下一个节点指向 nk。

所以,nk.next.next=nk

需要注意的是 n1的下一个节点必须指向 ∅。如果忽略了这一点,链表中可能会产生环。


三、代码

3.1 方法一:迭代(双指针)

Java版本:

class Solution {public ListNode reverseList(ListNode head) {ListNode cur = head, pre = null;while(cur != null) {ListNode tmp = cur.next; // 暂存后继节点 cur.nextcur.next = pre;          // 修改 next 引用指向pre = cur;               // pre 暂存 curcur = tmp;               // cur 访问下一节点}return pre;}
}

C++版本:

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode *cur = head, *pre = nullptr;while(cur != nullptr) {ListNode* tmp = cur->next; // 暂存后继节点 cur.nextcur->next = pre;           // 修改 next 引用指向pre = cur;                 // pre 暂存 curcur = tmp;                 // cur 访问下一节点}return pre;}
};

Python版本:

class Solution:def reverseList(self, head: ListNode) -> ListNode:cur, pre = head, Nonewhile cur:tmp = cur.next # 暂存后继节点 cur.nextcur.next = pre # 修改 next 引用指向pre = cur      # pre 暂存 curcur = tmp      # cur 访问下一节点return pre

3.2 方法二:递归

Java版本:

 public ListNode reverseList(ListNode head) {return recur(head, null);}private ListNode recur(ListNode cur, ListNode pre) {if (cur == null) return pre;ListNode res = recur(cur.next, cur);cur.next = pre;return res;}

C++版本:

class ListNode {
public: int val;ListNode* next;
};ListNode* reverseList(ListNode* head) {ListNode* pre = nullptr;ListNode* cur = head;while (cur) {ListNode* next = cur->next;cur->next = pre;pre = cur;cur = next;}return pre;
}

Python版本:

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverseList(head):def recur(cur, pre):if not cur:return preres = recur(cur.next, cur)cur.next = prereturn resreturn recur(head, None)

四、复杂度分析

4.1 方法一:迭代(双指针)

  • 时间复杂度 O(N) : 遍历链表使用线性大小时间。
  • 空间复杂度 O(1) : 变量 pre 和 cur 使用常数大小额外空间。

4.2 方法二:递归

  • 时间复杂度 O(N) : 遍历链表使用线性大小时间。
  • 空间复杂度 O(N) : 遍历链表的递归深度达到 N ,系统使用 O(N) 大小额外空间。

相关文章:

【数据结构和算法】反转链表

其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录 其他系列文章导航 文章目录 前言 一、题目描述 二、题解 2.1 方法一&#xff1a;迭代&#xff08;双指针&#xff09; 2.2 方法二&#xff1a;递归 三、代码 3.…...

What is `GenericFilterBean` does?

GenericFilterBean 是 SpringWeb 框架中提供的一个抽象基类&#xff0c;其对 javax.servlet.Filter接口进行了封装和扩展&#xff0c;它简化了在 Servlet环境下创建自定义过滤器的工作。 GenericFilterBean 主要特点包括&#xff1a; 集成 Spring 容器&#xff1a; 由于它是一…...

突破通胀风险,聚焦现货黄金投资机遇

随着全球经济不断发展和金融市场的波动&#xff0c;通胀风险成为各界关注的焦点。在面对通胀带来的财务压力和资产贬值的威胁时&#xff0c;投资者都在寻找稳定且可靠的避险资产。而现货黄金作为一种值得瞩目的投资工具&#xff0c;正吸引着越来越多投资者的目光。 黄金作为一种…...

Jenkins集成Sonar Qube

下载插件 重启Jenkins 容器 sonarqube 使用令牌 Jenkins 配置 重新构建...

Angular系列教程之zone.js和NgZone

文章目录 什么是zone.jsZone的工作原理Zone的常见用途NgZone&#xff1a;Angular中的zone.js使用NgZone使用NgZone执行代码使用NgZone外部检测 结论 什么是zone.js 在Angular中&#xff0c;zone.js是一个非常重要的库&#xff0c;它为我们提供了一种跟踪和管理异步操作的机制。…...

阿里巴巴的第二代通义千问可能即将发布:Qwen2相关信息已经提交HuggingFace官方的transformers库

本文来自DataLearnerAI官方网站&#xff1a;阿里巴巴的第二代通义千问可能即将发布&#xff1a;Qwen2相关信息已经提交HuggingFace官方的transformers库 | 数据学习者官方网站(Datalearner) 通义千问是阿里巴巴开源的一系列大语言模型。Qwen系列大模型最高参数量720亿&#xf…...

肯尼斯·里科《C和指针》第6章 指针(6)编程的练习:查找字符

1.编写一个函数&#xff0c;它在一个字符串中进行搜索&#xff0c;查找在一个给定字符集合中出现的所有字符。这个函数的原型如下&#xff1a; char *find_char( char const *source, char const *chars ); 它的基本想法是查找source字符串中匹配chars字符串中任何字符的第1个…...

Entity Framework知识点整理

Entity Framework Entity Framework&#xff08;EF&#xff09;是微软提供的一种对象关系映射&#xff08;Object-Relational Mapping&#xff0c;ORM&#xff09;框架&#xff0c;用于在.NET应用程序和关系型数据库之间建立映射关系。它简化了数据访问层的开发&#xff0c;使…...

源码搭建教学:连锁餐饮APP开发实战

连锁餐饮APP&#xff0c;对于很多从事餐饮行业的人来说不会陌生&#xff0c;同样这个项目本身就有着很高的热度。今天&#xff0c;小编将深入为大家讲述一下此系统的前后端开发、数据库设计、用户界面设计等方面&#xff0c;让您深入了解全栈开发的方方面面。 一、项目准备与规…...

使用JavaScript实现一个在线画板

一、引言 随着Web技术的发展&#xff0c;网页上的交互性变得越来越重要。一个在线画板是一个很好的例子&#xff0c;它允许用户在网页上自由创作。在这篇博客中&#xff0c;我们将使用HTML5的Canvas元素和JavaScript来实现一个简单的在线画板 二、HTML结构 首先&#xff0c;…...

微信小程序如何自定义导航栏,怎么确定导航栏及状态栏的高度?导航栏被刘海、信号图标给覆盖了怎么办?

声明&#xff1a;本文为了演示效果&#xff0c;颜色采用的比较显眼&#xff0c;可根据实际情况修改颜色 问题描述 当我们在JSON中将navigationStyle设置成custom后&#xff0c;当前页面的顶部导航栏就需要我们制作了&#xff0c;但出现了一下几个问题&#xff1a; 导航栏的高…...

Spring Boot “How-to“ 指南中文文档-上

本文为官方文档直译版本。原文链接 篇幅较长&#xff0c;遂分两篇 Spring Boot "How-to" 指南中文文档-上 引言Spring Boot Application创建自己的FailureAnalyzer&#xff08;故障分析器&#xff09;自动配置故障诊断启动前自定义环境或应用程序上下文构建 Applicat…...

快速了解spring boot中的@idempotent注解

目的&#xff1a;一定时间内&#xff0c;同样的请求(业务参数相同)访问同一个接口&#xff0c;则只能成功一次&#xff0c;其余被拒绝 幂等实现原理就是利用AOP面向切面编程&#xff0c;在执行业务逻辑之前插入一个方法&#xff0c;生成一个token&#xff0c;存入redis并插入到…...

【手把手带你玩转MyBatis】基础篇:挥洒自如的Java接口与注解

目录 1. MyBatis接口与Mapper接口 2. 注解属性解析 3. 使用接口实现数据访问 内容&#xff1a; 在MyBatis框架中&#xff0c;除了传统的XML映射文件方式之外&#xff0c;还支持使用Java接口和注解进行SQL映射。这种方式简化了开发流程&#xff0c;使得代码更简洁、直观&a…...

uniapp中u-switch子组件点击触发到父组件(阻止事件冒泡)

解决方法&#xff1a;在u-switch 外面包一个view标签&#xff0c;并使用tap.stop.prevent 可以阻止事件冒泡 .stop 阻止事件继续传播到父元素&#xff0c;prevent阻止事件默认行为 <view tap.stop.prevent><u-switch v-model"val_switch" change"cha…...

2024“华数杯”(A题)|放射性废水扩散|国际大学生数学建模竞赛建模解析,小鹿学长带队指引全代码文章与思路

我是小鹿学长&#xff0c;就读于上海交通大学&#xff0c;截至目前已经帮200人完成了建模与思路的构建的处理了&#xff5e; 完整内容可以在文章末尾领取&#xff01; 这回带大家体验一下2024“华数杯”国际大学生数学建模竞赛呀&#xff01; 此题涉及到放射性废水从日本排放…...

EtherCAT主站SOEM -- 16 --Qt-Soem通过界面按键控制电机转圈圈PV模式

EtherCAT主站SOEM -- 16 --Qt-Soem通过界面按键控制电机转圈圈 0 QT-SOEM视频预览及源代码下载:0.1 QT-SOEM视频预览0.2 QT-SOEM源代码下载1 程序文件修改替换1.1 allvalue.h1.2 motrorcontrol.h1.3 mainwindow.cpp1.4 motrorcontrol.cpp2 ui界面显示该文档修改记录:总结上下…...

芯品荟 | 电脑机箱键盘副屏市场调研报告

一.产品简介 1.带TFT彩屏电脑机箱 2.带小TFT彩屏电脑键盘 为什么电脑机箱&键盘&#xff0c;要带屏&#xff1f; 带屏的电脑机箱&键盘客户群体? 电竞玩家、设计师、电子发烧友、股民...... 二、市场规模 中国电脑机箱年产量约6000万台&#xff0c;键盘年产量约3亿…...

Mysql root 密码重置详解

文章目录 1 概述1.1 前言1.2 mysql 版本查询 2 windows 操作系统2.1 mysql 8 及以上版本2.1.1 关闭 mysql 服务2.1.2 通过无认证方式启动 mysql2.1.3 新开窗口&#xff0c;登录 mysql&#xff0c;重置密码 1 概述 1.1 前言 不同的操作系统&#xff08;如&#xff1a;windows、…...

微信小程序:发送小程序订阅消息

文档&#xff1a;小程序订阅消息&#xff08;用户通过弹窗订阅&#xff09;开发指南 目录 步骤一&#xff1a;获取模板 ID步骤二&#xff1a;小程序端获取参数2.1、获取消息下发权限2.2、获取登录凭证&#xff08;code&#xff09; 步骤三&#xff1a;后端调用接口下发订阅消息…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...