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

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

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

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

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解

文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一&#xff1a;HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二&#xff1a;Floyd 快慢指针法&#xff08;…...

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡 背景 我们以建设星云智控官网来做AI编程实践&#xff0c;很多人以为AI已经强大到不需要程序员了&#xff0c;其实不是&#xff0c;AI更加需要程序员&#xff0c;普通人…...

在Spring Boot中集成RabbitMQ的完整指南

前言 在现代微服务架构中&#xff0c;消息队列&#xff08;Message Queue&#xff09;是实现异步通信、解耦系统组件的重要工具。RabbitMQ 是一个流行的消息中间件&#xff0c;支持多种消息协议&#xff0c;具有高可靠性和可扩展性。 本博客将详细介绍如何在 Spring Boot 项目…...