数据结构 ——— 单链表oj题:反转链表

目录

题目要求

手搓一个简易链表

代码实现 


题目要求

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表


手搓一个简易链表

代码演示:

struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n1);
struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n2);
struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n3);
struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n4);
struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n5);n1->val = 1;
n2->val = 3;
n3->val = 5;
n4->val = 7;
n5->val = 9;n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = NULL;

代码实现

代码演示:

struct ListNode* reverseList(struct ListNode* head)
{if (head == NULL)return NULL;struct ListNode* prev = NULL;struct ListNode* cur = head;struct ListNode* next = cur->next;while (cur != NULL){cur->next = prev;// 迭代prev = cur;cur = next;if(next != NULL)next = next->next;}return prev;
}

代码解析:

代码思路:改变节点的指向,将单链表的第一个节点的 next 指向 NULL,第二个节点的 next 指向第一个节点,第三个节点的 next 指向第二个节点…………,以此类推,就完成了链表的反转

代码逻辑:利用一前(prev)一后(next)一中间(cur) 3 个节点指针进行迭代,将 cur 的 next 指向 prev,再依次往后赋值,需要注意的是 next 赋值为下一个节点的时候,要先判断 next 是否为空,再赋值,且结束的条件是中间节点为空,中间节点为空时就表示链表反转到位,最后再返回 prev 节点指针,就是新的头节点指针

代码验证:

代码的时间复杂度和空间复杂度:

while 循环执行了 N 次,每次内部是常数次,且没有开辟额外的空间,得出:

算法的时间复杂度(大O渐进表示法):O(N)

算法的空间复杂度(大O渐进表示法):O(1)

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

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

相关文章

1.2.2 计算机网络的分层结构(下)

水平视角 YSCS协议(压缩传输协议) 发送方先压缩然后接收方再解压。 为什么要分层?为什么要制定协议? 计算机网路功能负责->采用分层结构,将诸多功能合理地划分在不同层次->对等层之间制定协议,以…

如何彻底掌握 JavaScript 设计模式 23 大核心模式助你提升编程水平

如何彻底掌握 JavaScript 设计模式 23 大核心模式助你提升编程水平 设计模式是解决特定问题的常用解决方案,它们可以帮助开发者编写更清晰、可维护、可扩展的代码。在 JavaScript 中,常见的设计模式可以分为三大类:创建型模式、结构型模式 和…

什么样的孩子适合学C++?

随着科技的飞速发展,编程已成为许多家长和教育者重视的技能之一。在众多编程语言中,C因其强大的功能和广泛的应用,成为许多青少年学习编程的首选。然而,C相较于其他编程语言,如Python或Scratch,其学习难度更…

【书生浦语实战】茴香豆企业级知识库问答工具-搭建Dify问答助手

快速结论 1、用茴香豆快速搭建Dify问答助手,自带拒答、rerank、切片长度判断、阈值调节功能,回答还能带出图片,顶呱呱👍 2、茴香豆git仓地址:https://github.com/internlm/huixiangdou 遇到问题去翻这里会更多解释&…

【Linux探索学习】第三弹——Linux的基础指令(下)——开启新篇章的大门

Linux基础指令(上): 【Linux探索学习】第一弹——Linux的基本指令(上)——开启Linux学习第一篇-CSDN博客 Linux基础指令(中): 【Linux探索学习】第二弹——Linux的基础指令&#…

MySQL多表查询:列子查询

先看我的表数据 dept表 emp表 列子查询,也就是多列作为子查询去寻找一些问题 常用操作符:IN, NOT IN, ANY, SOME, ALL 1.查询 "销售部" 和 "市场部" 的所有员工的信息(拆分成以下两个问题) a. 查询"销…

[Python学习日记-40] 函数进阶之装饰器

[Python学习日记-40] 函数进阶之装饰器 简介 引子 什么是装饰器 装饰器终结版 装饰器的层层叠加 简介 在前面铺垫了这么多终于该讲到重点了,前面说的匿名函数、高阶函数、闭包等等都是为了这篇文章所讲的装饰器而使用的,本篇文章将会一一个故事通俗…

Redis:list类型

Redis:list类型 list命令非阻塞LPUSHLRANGELPUSHXRPUSHRPUSHXLPOPRPOPLINDEXLINSERTLLENLREMLTRIMLSET 阻塞BLPOPBRPOP 内部编码ziplistlinkedlistquicklist 几乎每种语言都有顺序表、数组、链表这样的顺序结构,Redis也做出了相应的支持。 如图&#xff…

案例-博客页面简单实现

文章目录 本文内容只涉及前端1. 内容要求2. 画面展示初始化面演示视频 3. 注意事项4. 代码区js文件夹下的jquery.min.js内容登录代码列表页面创作页面 本文内容只涉及前端 1. 内容要求 登录页面实现博客列表页面实现博客创作页面实现 链接: 开源在线 Markdown 编辑器文本框可…

MATLAB智能优化算法-学习笔记(4)——灰狼优化算法求解旅行商问题【过程+代码】

灰狼优化算法(Grey Wolf Optimizer, GWO)是一种基于灰狼社会行为的元启发式算法,主要模拟灰狼群体的捕猎行为(包括围攻、追捕、搜寻猎物等过程)。多旅行商问题(Multi-Traveling Salesman Problem, mTSP)是旅行商问题(TSP)的扩展,它涉及多个旅行商(车辆)从一个起点城…

免杀对抗—javaASMMSF源码特征修改汇编调用CS内联C

前言 今天讲最后的两个语言java和汇编,那么基本所有语言就讲了一个遍了。java在后门免杀这一块呢其实是有点鸡肋的,其它语言编译成的是exe,而java编译成的是jar包,而jar包又得有java环境才能运行,不像exe是个电脑都行…

C++ : STL容器之string剖析

STL容器之string剖析 一、string 的迭代器(一)起始迭代器(二)末尾迭代器(三)反向迭代器 二、容量相关的函数(一)size(二)capacity(三)…

【java】数据类型与变量以及操作符

各位看官:如果您觉得这篇文章对您有帮助的话 欢迎您分享给更多人哦 感谢大家的点赞收藏评论,感谢您的支持!!! 目录 一.字面变量: 二:数据类型 1.1:int类型:&#xff0…

无人机(自组穿越机,航模)-芯片选型

飞控MCU: 型号尺寸子型号参数规格备注STM325*532位ARM Cortex-M3 CPU,72MHz,256KB Flash,20KB RAMLQFP 48F33*332位ARM Cortex-M4 CPU,72MHz,256KB Flash,40KB RAMMPU6050F45*532位ARM Cortex-M4 CPU&…

github学生认证(Github Copilot)

今天想配置一下Github Copilot,认证学生可以免费使用一年,认证过程中因为各种原因折腾了好久,记录一下解决方法供大家参考。 p.s.本文章只针对Github学生认证部分遇到的问题及解决方法,不包括配置copilot的全部流程~ 1、准备工作…

如何使用ssm实现基于Java的校园二手物品交易平台的设计与实现+vue

TOC ssm789基于Java的校园二手物品交易平台的设计与实现vue 绪论 1.1 研究背景 在这个推荐个性化的时代,采用新技术开发一个校园二手物品交易平台来分享和展示内容是一个永恒不变的需求。本次设计的校园二手物品交易平台有管理员,商家,用…

Git大框架总结

下面首先是我对于git的一个小总结,主要是大框架 首先是四区,因为大部分你所有的工作都是在这四个区里的实现的,包括要提交一个东西,是先是在工作区修改,后用add添加到暂存区,后提交到本地仓库,当…

系统架构设计师论文《论企业应用系统的分层架构风格》精选试读

论文真题 软件架构风格是描述一类特定应用领域中系统组织方式的惯用模式,反映了领域中诸多系统所共有的结构特征和语义特征,并指导如何将各个模块和子系统有效组织成一个完整的系统。分层架构是一种常见的软件架构风格,能够有效简化设计&…

基于WxJava框架的集客微信公众号的设计与实现(项目运行说明)

项目运行说明 数据库 系统采用MySQL数据库和Redis数据库,读者可参考在码云项目(code/yok/src/main/resources)中的application.yml中自行配置MySQL数据库,在redis.properties中配置Redis。 数据库表的创建语句在yok项目中的create_dataBase.sql文件中。 项目启动 后端项目…

JAVA思维提升

利用java做一个双色球彩票系统 要求 package ZY; import java.util.Random; import java.util.Scanner; public class Test9双色球 { //目标:模拟双色球//规则投注号码由6个红色球号码和1个蓝色球号码组成。红色球号码从1-33中选择;蓝色球号码从1-16中选择。publi…