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

news/2024/2/24 6:57:53/文章来源:https://blog.csdn.net/kologin/article/details/135641759

其他系列文章导航

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) 大小额外空间。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_925874.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

survey和surveyCV:如何用R语言进行复杂抽样设计、权重计算和10折交叉验证?

一、引言 在实际调查和研究中&#xff0c;我们往往面临着样本选择的复杂性。复杂抽样设计能够更好地反映真实情况&#xff0c;提高数据的代表性和可靠性。例如&#xff0c;多阶段抽样可以有效地解决大规模调查的问题&#xff0c;整群抽样能够在保证样本的随机性的同时减少资源消…

网络安全全栈培训笔记(53-WEB攻防-通用漏洞跨域CORS资源JSONP回调域名接管劫持)

第54天 WEB攻防-通用漏洞&跨域CORS资源&JSONP回调&域名接管劫持 知识点&#xff1a; 1、子域名接管检测&探针&利用 2、C0SP跨域资源检测&探针&利用 3、JSONP跨域回调-检侧&探针&利用 #前置知识点&#xff1a; 同源策路(SOP),“同源”包…

centos7配置时间同步网络时间

centos7配置时间同步网络时间 1、安装 NTP 工具。 sudo yum install -y ntp2启动 NTP 服务。 sudo systemctl start ntpd3、将 NTP 服务设置为开机自启动。 sudo systemctl enable ntpd4、验证 date

【特征工程】分类变量:MultiLabelBinarizer对多标签数据进行编码

MultiLabelBinarizer 说明介绍 1. MultiLabelBinarizer 是什么&#xff1f; MultiLabelBinarizer是scikit-learn库中的一个用于处理多标签数据的编码器。通常用于将多标签的分类任务中的标签转化为二进制形式&#xff0c;便于机器学习模型的处理。该编码器的主要目标是将每个…

【网络安全】【密码学】【北京航空航天大学】实验一、数论基础(上)【C语言和Java实现】

实验一、数论基础&#xff08;上&#xff09; 一、实验目的 1、通过本次实验&#xff0c;熟悉相关的编程环境&#xff0c;为后续的实验做好铺垫&#xff1b; 2、回顾数论学科中的重要基本算法&#xff0c;并加深对其的理解&#xff0c;为本学期密码学理论及实验课程打下良好…

《ARM Linux内核源码剖析》读书笔记——0号进程(init_task)的创建时机

最近在读《ARM Linux内核源码剖析》&#xff0c;一直没有看到0号进程&#xff08;init_task进程)在哪里创建的。直到看到下面这篇文章才发现书中漏掉了set_task_stack_end_magic(&init_task)这行代码。 下面这篇文章提到&#xff1a;start_kernel()上来就会运行 set_task_…

如何用MetaGPT帮你写一个贪吃蛇的小游戏项目

如何用MetaGPT帮你写一个贪吃蛇的小游戏项目 MetaGPT是基于大型语言模型(LLMs)的多智能体写作框架&#xff0c;目前在Github开源&#xff0c;其Start数量也是比较高的&#xff0c;是一款非常不错的开源框架。 下面将带你进入MetaGPT的大门&#xff0c;开启MetaGPT的体验之旅。…

大创项目推荐 深度学习手势识别算法实现 - opencv python

文章目录 1 前言2 项目背景3 任务描述4 环境搭配5 项目实现5.1 准备数据5.2 构建网络5.3 开始训练5.4 模型评估 6 识别效果7 最后 1 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 深度学习手势识别算法实现 - opencv python 该项目较为新颖…

推荐一个页面引导库 driver.js

页面引导功能是 web 开发中常见的一个功能。通过页面引导功能&#xff0c;你可以让用户第一时间熟悉你的页面功能。今天给大家推荐一个页面引导库 driver.js。 简介 driver.js 是一款用原生 js 实现的页面引导库&#xff0c;上手非常简单&#xff0c;体积在 gzip 压缩下仅仅 5…

MongoDB面试系列-01

1. MongoDB 是什么&#xff1f; MongoDB是由C语言编写的&#xff0c;是一个基于分布式文件存储的开源数据库系统。再高负载的情况下&#xff0c;添加更多的节点&#xff0c;可以保证服务器性能。MongoDB旨在给Web应用提供可扩展的高性能数据存储解决方案。 MongoDB将数据存储…

Shopify绑定Facebook收费吗?付款方式是什么?-站斧浏览器

Shopify绑定Facebook收费吗&#xff1f; 答案是&#xff1a;Shopify绑定Facebook并不收取额外费用。Shopify和Facebook之间的绑定是免费的&#xff0c;卖家可以充分利用这一功能来扩展他们的在线业务。通过将商店与Facebook Page相连接&#xff0c;卖家可以将产品目录同步到Fa…

LeetCode 41 缺失的第一个正数

题目描述 缺失的第一个正数 给你一个未排序的整数数组 nums &#xff0c;请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,0] 输出&#xff1a;3示例 2&#xff…

rabbitmq-java基础详解

一、rabbitmq是什么&#xff1f; 1、MQ定义 MQ&#xff08;Message Queue&#xff09;消息队列 主要解决&#xff1a;异步处理、应用解耦、流量削峰等问题&#xff0c;是分布式系统的重要组件&#xff0c;从而实现高性能&#xff0c;高可用&#xff0c;可伸缩和最终一致性的架…

NLP技术在搜索推荐场景中的应用

NLP技术在搜索推荐中的应用非常广泛&#xff0c;例如在搜索广告的CTR预估模型中&#xff0c;NLP技术可以从语义角度提取一些对CTR预测有效的信息&#xff1b;在搜索场景中&#xff0c;也经常需要使用NLP技术确定展现的物料与搜索query的相关性&#xff0c;过滤掉相关性较差的物…

CASAIM与LG化学越南工厂达成全自动化智能测量技术合作,助力汽车锂电池相关零部件全自动化测量及质量管控

近日&#xff0c;CASAIM与LG化学越南工厂达成全自动化智能测量技术合作&#xff0c;CASAIM将为LG化学越南工厂提供最新一代的CASAIM-IS全自动化测量系统解决方案&#xff0c;助力LG化学越南工厂实现汽车锂电池相关零部件的高精度、高效率测量和检测&#xff0c;进一步提升产品质…

【Vue】后端返回文件流,前端预览文件

let date;request({url: this.$route.query.url,method: get,responseType: blob,}).then(resp > {date respthis.path window.URL.createObjectURL(new Blob([resp], {type: "application/pdf"}))}).catch((e) > {//旧版本浏览器下的blob创建对象window.Blo…

Langchain 与 Elasticsearch:创新数据检索的融合实战

1、简介 在信息爆炸的时代&#xff0c;有效地检索和处理数据变得至关重要。Langchain 和 Elasticsearch 的结合&#xff0c;为我们提供了一个强大的工具&#xff0c;以更智能的方式进行数据检索和分析。 作为一名拥有多年 Elasticsearch 实战经验的技术博主&#xff0c;我将在本…

注意:温度太高电路板表面会氧化导致不上锡

不上锡的情况为什么大多发生在热天&#xff1f; 因为天气太热&#xff0c;室内和室外温差太大&#xff0c;如把PCB板从30多度的室外转移到温度更低的室内就会导致PCB板表面“流汗”现象&#xff0c;PCB板表面有水份就会让其氧化PCB板拆封后&#xff0c;SMT工厂内部环境不好或温…

DC电源模块在新能源领域的应用前景

BOSHIDA DC电源模块在新能源领域的应用前景 DC电源模块在新能源领域有着广阔的应用前景。随着可再生能源技术的发展和普及&#xff0c;如太阳能和风能等的应用逐渐增多&#xff0c;DC电源模块在这些领域的应用越来越重要。 首先&#xff0c;DC电源模块可以用于太阳能发电系统…

记一次 .NET某收银软件 非托管泄露分析

一&#xff1a;背景 1. 讲故事 在我的分析之旅中&#xff0c;遇到过很多程序的故障和杀毒软件扯上了关系&#xff0c;有杀毒软件导致的程序卡死&#xff0c;有杀毒软件导致的程序崩溃&#xff0c;这一篇又出现了一个杀毒软件导致的程序非托管内存泄露&#xff0c;真的是分析多…