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

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

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

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

Spring数据访问模块设计

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

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...