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

翻转链表(力扣刷题)

给你单链表的头节点 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
 

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/reverse-linked-list

思路:

        如果再定义一个新的链表,实现链表元素的反转,其实这是对内存空间的浪费。

        其实只需要改变链表的next指针的指向,直接将链表反转 ,而不用重新定义一个新的链表,如图所示:

        之前链表的头节点是元素1, 反转之后头结点就是元素5 ,这里并没有添加或者删除节点,仅仅是改变next指针的方向。

        那么接下来看一看是如何反转的呢?

         首先定义一个cur指针,指向头结点,再定义一个pre指针,初始化为null。

然后就要开始反转了,首先要把 cur->next 节点用tmp指针保存一下,也就是保存一下这个节点。

        为什么要保存一下这个节点呢,因为接下来要改变 cur->next 的指向了,将cur->next 指向pre ,此时已经反转了第一个节点了。

        接下来,就是循环走如下代码逻辑了,继续移动pre和cur指针。

        最后,cur 指针已经指向了null,循环结束,链表也反转完毕了。 此时我们return pre指针就可以了,pre指针就指向了新的头结点。

这里列举了两种方式:

①双指针法

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* temp; // 保存cur的下一个节点ListNode* cur = head;ListNode* pre = NULL;while(cur) {temp = cur->next;  // 保存一下 cur的下一个节点,因为接下来要改变cur->nextcur->next = pre; // 翻转操作// 更新pre 和 cur指针pre = cur;cur = temp;}return pre;}
};

 ②递归法:

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* temp; // 保存cur的下一个节点ListNode* cur = head;ListNode* pre = NULL;while(cur) {temp = cur->next;  // 保存一下 cur的下一个节点,因为接下来要改变cur->nextcur->next = pre; // 翻转操作// 更新pre 和 cur指针pre = cur;cur = temp;}return pre;}
};

        我们可以发现,上面的递归写法和双指针法实质上都是从前往后翻转指针指向,其实还有另外一种与双指针法不同思路的递归写法:从后往前翻转指针指向。

代码如下:

class Solution {
public:ListNode* reverseList(ListNode* head) {// 边缘条件判断if(head == NULL) return NULL;if (head->next == NULL) return head;// 递归调用,翻转第二个节点开始往后的链表ListNode *last = reverseList(head->next);// 翻转头节点与第二个节点的指向head->next->next = head;// 此时的 head 节点为尾节点,next 需要指向 NULLhead->next = NULL;return last;}
}; 

相关文章:

翻转链表(力扣刷题)

给你单链表的头节点 head &#xff0c;请你反转链表&#xff0c;并返回反转后的链表。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5] 输出&#xff1a;[5,4,3,2,1] 示例 2&#xff1a; 输入&#xff1a;head [1,2] 输出&#xff1a;[2,1] 示例 3&#xff1a; 输入…...

JavaEE——锁相关

在开发过程中&#xff0c;如果需要开发者自主实现一把锁&#xff0c;就必须了解锁策略和锁的实现原理。 目录 锁策略 乐观锁和悲观锁 互斥锁和读写锁 轻量级锁和重量级锁 自旋锁和挂起等待锁 公平锁和非公平锁 可重入锁和不可重入锁 死锁 发生死锁的必要条件 synchr…...

C语言指针与数组 进阶

本章主要是补充 指针和数组方面的指示&#xff0c;把前面指针的知识补充下。参考前面的C语言基础—指针 C语言指针与数组 进阶用一级指针访问二维数组❗易错点: 不能直接指针变量数组名指向数组的指针1. 指向指针的指针2. 指向一维数组的指针 (*P)[4]—行指针二维数组名指针数组…...

Java连接SqlServer错误

Java连接SqlServer错误 &#x1f3e0;个人主页&#xff1a;shark-Gao &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是shark-Gao&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f389;目前状况&#xff1a;23届毕业生&#xff0c;目…...

Elastic 可观察性 - 适用于当今 “永远在线” 世界的解决方案

作者&#xff1a;Bahubali Shetti 当今世界&#xff0c;我们的生活很大程度上由应用程序控制。 无论是用于商业用途还是个人用途&#xff0c;我们都希望这些应用程序 “始终在线” 并能够立即做出响应。 这些高期望对开发人员和运营人员提出了巨大的要求。 管理这些应用程序需…...

Temu病毒式营销,如何在大红利时期快人一步?

从去年9月开始&#xff0c;拼多多推出海外版Temu&#xff0c;大手笔烧钱买量、大手笔补贴消费者&#xff0c;通过令人难以置信的超低价&#xff08;比如一件卫衣2.44美元&#xff0c;且包邮&#xff09;&#xff0c;在北美市场迅速打开局面&#xff0c;并引发海外网友“人传人”…...

ChatGPT使用案例之写代码

ChatGPT使用案例之写代码 可以对于许多开发者而言又惊又喜的是我们可以使用ChatGPT 去帮我们完成一些代码&#xff0c;或者是测试用例的编写&#xff0c;但是正如我们提到的又惊又喜&#xff0c;可能开心的是可以解放一部分劳动力&#xff0c;将自己的精力从繁琐无聊的一些任务…...

蓝桥杯刷题第二十五天

第一题:全球变暖 题目描述 你有一张某海域 NxN 像素的照片&#xff0c;"."表示海洋、"#"表示陆地&#xff0c;如下所示&#xff1a; ....... .##.... .##.... ....##. ..####. ...###. ....... 其中"上下左右"四个方向上连在一起的一片陆地组成一…...

【牛客网】

目录知识框架No.1 前缀和NC14556&#xff1a;数圈圈NC14600&#xff1a;珂朵莉与宇宙NC21195 &#xff1a;Kuangyeye and hamburgersNC19798&#xff1a;区间权值NC16730&#xff1a;runNC15035&#xff1a;送分了qaqNo.2 字符串&#xff1a;小知识点&#xff1a;基于KMP算法的…...

SpringBoot中的事务

事务 Springboot有3种技术方式来实现让加了Transactional的方法能使用数据库事务&#xff0c;分别是"动态代理(运行时织入)"、“编译期织入”和“类加载期织入”。这3种技术都是基于AOP(Aspect Oriented Programming&#xff0c;面向切面编程)思想。&#xff08;在网…...

Zookeeper客户端Curator5.2.0节点事件监听CuratorCache用法

Curator提供了三种Watcher&#xff1a; &#xff08;1&#xff09;NodeCache&#xff1a;监听指定的节点。 &#xff08;2&#xff09;PathChildrenCache&#xff1a;监听指定节点的子节点。 &#xff08;3&#xff09;TreeCache&#xff1a;监听指定节点和子节点及其子孙节点。…...

C++ using:软件设计中的面向对象编程技巧

C using:理解头文件与库的使用引言using声明a. 使用方法和语法b. 实际应用场景举例i. 避免命名冲突ii. 提高代码可读性c. 注意事项和潜在风险using指令a. 使用方法和语法b. 实际应用场景举例i. 将整个命名空间导入当前作用域ii. 代码组织和模块化using枚举a. C11的新特性b. 使用…...

修建灌木顺子日期

题目 有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晩会修剪一棵灌 木, 让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始, 每天向右修剪一棵灌木。当修剪了最右侧的灌木后, 她会调转方向, 下一天开 始向左修剪灌木。直到修剪了最左的灌木后再次调转方…...

深入学习JavaScript系列(七)——Promise async/await generator

本篇属于本系列第七篇 第一篇&#xff1a;#深入学习JavaScript系列&#xff08;一&#xff09;—— ES6中的JS执行上下文 第二篇&#xff1a;# 深入学习JavaScript系列&#xff08;二&#xff09;——作用域和作用域链 第三篇&#xff1a;# 深入学习JavaScript系列&#xff…...

Mybatis中的Map的使用和模糊查询的需求实现及其防SQL注入优化

文章目录一.Map的使用和模糊查询的需求实现及其防SQL注入优化1.1 Map的使用1.2 模糊查询的实现1.2.1 防SQL注入优化1.2.2 总结一.Map的使用和模糊查询的需求实现及其防SQL注入优化 1.1 Map的使用 替换之前的根据ID查询信息&#xff1a; 1.编写接口&#xff1a; User getUse…...

【redis】redis缓存更新策略

目录一、缓存更新策略二、主动更新策略三、Cache Aside Pattern3.1 删除缓存还是更新缓存?3.2 如何保证缓存与数据库的操作同时成功或失败&#xff1f;3.3 先操作缓存还是先操作数据库3.3.1 先删缓存再删库3.3.2 先删库再删缓存一、缓存更新策略 1.内存淘汰&#xff1a;不用自…...

LeetCode刷题--复制带随机指针的链表

复制带随机指针的链表1.题目2.解题思路3.完整代码1.题目 题目链接: https://leetcode.cn/problems/copy-list-with-random-pointer/ 给你一个长度为 n 的链表&#xff0c;每个节点包含一个额外增加的随机指针 random &#xff0c;该指针可以指向链表中的任何节点或空节点。 …...

关于我的第一台电脑 华硕

2011年买的&#xff0c;第一台电脑是华硕 U36KI243SD 13.3英寸 白色 i5 1G独显 USB3.0 500G 当时花了5699&#xff0c;着实是一笔巨款&#xff0c;我同学看了一眼就说“我C&#xff0c;这本真好”。 买它主要还是因为好看。当时win7也才开始流行&#xff0c;感觉用上这个本&…...

【华为OD机试 2023最新 】 最大化控制资源成本(C++ 100%)

文章目录 题目描述输入描述输出描述备注用例题目解析C++题目描述 公司创新实验室正在研究如何最小化资源成本,最大化资源利用率,请你设计算法帮他们解决一个任务混部问题: 有taskNum项任务,每个任务有开始时间(startTime),结束时间(endTime),并行度(parallelism)…...

leetcode 有序数组的平方(977)

题目 给你一个按 非递减顺序 排序的整数数组 nums&#xff0c;返回 每个数字的平方 组成的新数组&#xff0c;要求也按 非递减顺序 排序。 示例 1&#xff1a; 输入&#xff1a;nums [-4,-1,0,3,10] 输出&#xff1a;[0,1,9,16,100] 解释&#xff1a;平方后&#xff0c;数组变…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

LOOI机器人的技术实现解析:从手势识别到边缘检测

LOOI机器人作为一款创新的AI硬件产品&#xff0c;通过将智能手机转变为具有情感交互能力的桌面机器人&#xff0c;展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家&#xff0c;我将全面解析LOOI的技术实现架构&#xff0c;特别是其手势识别、物体识别和环境…...

上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式

简介 在我的 QT/C 开发工作中&#xff0c;合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式&#xff1a;工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践

在 Kubernetes 集群中&#xff0c;如何在保障应用高可用的同时有效地管理资源&#xff0c;一直是运维人员和开发者关注的重点。随着微服务架构的普及&#xff0c;集群内各个服务的负载波动日趋明显&#xff0c;传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...

高防服务器价格高原因分析

高防服务器的价格较高&#xff0c;主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因&#xff1a; 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器&#xff0c;因此…...

二维FDTD算法仿真

二维FDTD算法仿真&#xff0c;并带完全匹配层&#xff0c;输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...

统计学(第8版)——统计抽样学习笔记(考试用)

一、统计抽样的核心内容与问题 研究内容 从总体中科学抽取样本的方法利用样本数据推断总体特征&#xff08;均值、比率、总量&#xff09;控制抽样误差与非抽样误差 解决的核心问题 在成本约束下&#xff0c;用少量样本准确推断总体特征量化估计结果的可靠性&#xff08;置…...