(链表) 剑指 Offer 24. 反转链表 ——【Leetcode每日一题】

news/2024/4/16 2:18:45

❓剑指 Offer 24. 反转链表

难度:简单

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制

  • 0 <= 节点个数 <= 5000

注意:本题与 206. 反转链表 相同。

💡思路:

法一:递归

可以将本问题分解成子问题:

  • 1->(剩余部分的反转),而1 始终指向 2,即1->2
  • 所以第一层递归的结果以为: 5->4->3->2 <-1
  • 每一层以此类推。

法二:迭代

  • 头插法。

🍁代码:(C++、Java)

法一:递归
C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {if(head == nullptr || head->next == nullptr) return head;ListNode* temp = reverseList(head->next);head->next->next = head;head->next = nullptr;return temp;}
};

Java

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode reverseList(ListNode head) {if(head == null || head.next == null) return head;ListNode temp = reverseList(head.next);head.next.next = head;head.next = null;return temp;}
}

法二:迭代
C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* h0 = new ListNode(-1);ListNode* temp = head;while(head != nullptr){head = head->next;temp->next = h0->next;h0->next = temp;temp = head;}head = h0->next;delete(h0);return head;}
};

Java

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode reverseList(ListNode head) {ListNode h0 = new ListNode(-1);ListNode temp = head;while(head != null){head = head.next;temp.next = h0.next;h0.next = temp;temp = head;}head = h0.next;return head;}
}

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 n 为链表的长度。
  • 空间复杂度 O ( 1 ) O(1) O(1),递归空间复杂度为 O ( n ) O(n) O(n),主要取决于递归调用的栈空间,最多为 n 层。而迭代只需要常数级额外空间,即为 O ( 1 ) O(1) O(1)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/979959.html

相关文章

经营简报echarts图

文章目录 效果图代码 效果图 代码 <template><div class"mainFirst"><div id"main" style"width: 100%; height: 500px"></div></div> </template><script> import * as echarts from "echarts…

Swift 中如何判断是push 过来的页面 还是present过来的 页面

在 Swift 中&#xff0c;可以通过检查当前视图控制器的 presentingViewController 属性来判断是通过 push 过来的页面还是 present 过来的页面。 下面是一个示例代码&#xff0c;展示如何判断是通过 push 还是 present 过来的页面&#xff1a; if let presentingViewControll…

mysql(二)SQL语句

目录 一、SQL语句类型 二、数据库操作 三、数据类型 四、创建 五、查看 六、更改 七、增、删、改、查 八、查询数据 一、SQL语句类型 SQL语句类型&#xff1a; DDL DDL&#xff08;Data Definition Language&#xff0c;数据定义语言&#xff09;&#xff1a;用于…

初探PID—速度闭环控制

由于在调PID时意外把板子烧了&#xff0c;目前只完成了比例调节的调试&#xff0c;整个程序也不太完善&#xff0c;本文当前仅作记录&#xff0c;后续会完善更改。 ——2023.07.26 文章目录 一、什么是PID二、PID有什么用三、PID程序实现 一、什么是PID PID是常用的一种控制算…

pipeline和retiming

首先,pipeline 是 rtl design 的技巧,Retiming 是 synthesize 的技术。设计里面要有pipeline,才有后面的retiming。 当然,現在synthesis 进步很多了,這句话在有些时候已经不成立了,但是,大多数的时候,Retiming 还是针对pipeline 做优化。 一個简单的例子,例如我们做一…

全面解析 SOCKS5 代理与 HTTP 代理的对比与应用

一、 SOCKS5 代理与 HTTP 代理的基本原理 SOCKS5 代理&#xff1a;SOCKS5 是一种网络协议&#xff0c;它可以在传输层&#xff08;Transport Layer&#xff09;代理 TCP 和 UDP 请求。SOCKS5 代理不解析请求内容&#xff0c;而是直接将数据中转至目标服务器&#xff0c;支持更广…

华为eNSP:isis配置跨区域路由

一、拓扑图 二、路由器的配置 1、配置接口IP AR1: <Huawei>system-view [Huawei]int g0/0/0 [Huawei-GigabitEthernet0/0/0]ip add 1.1.1.1 24 [Huawei-GigabitEthernet0/0/0]q AR2: [Huawei]int g0/0/0 [Huawei-GigabitEthernet0/0/0]ip add 1.1.1.2 24 [Huawe…

C# OpenCvSharpe 二值化工具 阈值 自适应阈值 局部阈值 InRange

效果 阈值 自适应阈值 局部阈值 InRange 项目 VS2010.net4.0OpenCvSharper3 Demo下载

json-server创建静态服务器2

上次写的 nodejs创建静态服务器 这次再来个v2.0 利用json-server很方便就可以实现。 vscode打开文件夹&#xff0c;文件夹所在终端&#xff1a; json-server.cmd --watch db.json 这里视频教程是没有上述命令标红的&#xff0c;但是会报错&#xff0c;具体不详&#xff0c…

opencv-20 深入理解HSV 色彩空间(通过指定,标记颜色等来拓展ROI区域)

RGB 色彩空间是一种被广泛接受的色彩空间&#xff0c;但是该色彩空间过于抽象&#xff0c;我们不能够直接通过其值感知具体的色彩。 我们更习惯使用直观的方式来感知颜色&#xff0c;HSV 色彩空间提供了这样 的方式。 通过 HSV色彩空间&#xff0c;我们能够更加方便地通过色调、…

【数据库 - 用户权限管理】(简略)

目录 一、概述 二、用户权限类型 1.ALL PRIVILEGES 2.CREATE 3.DROP 4.SELECT 5.INSERT 6.UPDATE 7.DELETE 8.INDEX 9.ALTER 10.CREATE VIEW和CREATE ROUTINE 11.SHUTDOWN 12GRANT OPTION 三、语句格式 1.用户赋权 2.权限删除 3.用户删除 一、概述 数据库用…

子类化QThread来实现多线程,moveToThread函数的作用

子类化QThread来实现多线程&#xff0c; QThread只有run函数是在新线程里的&#xff0c;其他所有函数都在QThread生成的线程里。正确启动线程的方法是调用QThread::start()来启动。 一、步骤 子类化 QThread&#xff1b;重写run&#xff0c;将耗时的事件放到此函数执行&#…

vue 图片的引入方式

一、import 静态引入 放在script标签顶端 例如 import errowPng from ../../assets/404_images/404.png 二、require 动态引入 可以放在data中 data() {return {imgUrl:require("../../assets/404_images/404.png")};}, require 是赋值过程并且是运行时才执行&…

OpenShift 4 - 为 OpenShift 托管集群配置用户认证(视频)

《OpenShift / RHEL / DevSecOps / Ansible 汇总目录》 说明&#xff1a;本文已经在 OpenShift 4.13 ACM 2.8 AWS 环境中验证 本文是《OpenShift 4 - 用 HyperShift 实现以“托管集群”方式部署运行 OpenShift 集群&#xff08;视频&#xff09;》的后续。 文章目录 托管集群…

九、数据结构——顺序队列中的循环队列

目录 一、循环队列的定义 二、循环队列的实现 三、循环队列的基本操作 ①初始化 ②判空 ③判满 ④入队 ⑤出队 ⑥获取长度 ⑦打印 四、循环队列的应用 五、全部代码 数据结构中的循环队列 在数据结构中&#xff0c;队列&#xff08;Queue&#xff09;是一种常见的线性数据结…

Python 基础总结

title: Python 基础总结 date: 2023-07-19 10:51:55 tags: Python categories:Python cover: https://cover.png feature: false 1. print() 函数 1.1 基础使用 # 输出数字 print(23) print(11.323)# 输出字符串 print(你好) print("你好")# 输出表达式 print(3 *…

windows串口被用占用问题解决方案

1、进入注册表&#xff1a;regedit 2、修改注册表&#xff0c;删除多余的串口 详见&#xff1a;Win10清除COM接口占用_清除com端口占用_南河小翁的博客-CSDN博客

三层交换基础实验

要求: 1.IP地址基于192.168.1.0/24划分 2.使用OSPF 3.使用DHCP 4.全网可达 1.配置二层交换 SW 3 <Huawei>system-view [Huawei]sysname SW3 [SW3]interface GigabitEthernet 0/0/2 [SW3-GigabitEthernet0/0/2]port link-type access [SW3-GigabitEthernet0/0/2]por…

管理类联考——数学——记忆篇——不同角度解读——四、数据分析——1.计数原理/排列组合

计数原理 1.计数原理 1.1 加法原理、乘法原理 1.2 排列与排列数 1.3 组合与组合数 PS&#xff1a;图标说明 ⛲️&#xff1a;陈jian &#x1f475;&#xff1a;鑫quan &#x1f469;&#xff1a;张紫chao &#x1f482;&#xff1a;MBA大shi &#x1f63d;&#xff1a;海mian…

灾备基础学习

灾备 灾备&#xff1a;灾备是容灾和备份的简称&#xff0c;它是利用科学的技术手段和方法&#xff0c;提前建立系统化的数据应急方式&#xff0c;以应对灾难的发生。其内容包括&#xff1a;数据备份、系统备份、业务连续规划、人员架构、通信保障、危机公关、灾难恢复规划、灾…
最新文章