每日一题:BM1 反转链表
文章目录
- @[toc]
- 问题描述
- 数据范围
- 示例
- C++代码实现
- 使用栈实现(不符合要求,仅作为思路)
- 解题思路 - 原地反转链表
- 步骤
- C语言代码实现
文章目录
- @[toc]
- 问题描述
- 数据范围
- 示例
- C++代码实现
- 使用栈实现(不符合要求,仅作为思路)
- 解题思路 - 原地反转链表
- 步骤
- C语言代码实现
以前只用过C++刷过代码题目,现在试着用C语言刷下
问题描述
给定一个单链表的头结点 pHead,反转该链表后返回新链表的表头。

数据范围
- 链表长度 0 ≤ n ≤ 1000 0 \leq n \leq 1000 0≤n≤1000
- 要求:空间复杂度 O ( 1 ) O(1) O(1),时间复杂度 O ( n ) O(n) O(n)
示例
-
输入:
{1,2,3}
输出:{3,2,1} -
输入:
{}
输出:{}
如果链表为空,则直接返回空。
C++代码实现
最开始尝试用 C++ 的 栈 实现,结果想到C语言不能直接调用栈,玛德。但考虑到题目要求空间复杂度为 O ( 1 ) O(1) O(1),栈的实现并不符合要求。
使用栈实现(不符合要求,仅作为思路)
#include <stack>
#include <iostream>
using namespace std;// 定义链表节点
struct ListNode {int val;struct ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};// 使用栈实现链表反转
struct ListNode* ReverseList(struct ListNode* head) {if (head == nullptr) // 空链表直接返回return head;stack<ListNode*> st; // 定义一个栈ListNode* cur = head;// 将所有节点压入栈while (cur != nullptr) {st.push(cur);cur = cur->next;}// 弹出栈顶元素作为新链表头ListNode* newHead = st.top();st.pop();cur = newHead;// 重新连接链表while (!st.empty()) {cur->next = st.top();st.pop();cur = cur->next;}cur->next = nullptr; // 终止链表return newHead;
}
此代码能实现反转,但使用了辅助栈,空间复杂度为 O ( n ) O(n) O(n),不符合题目要求。
解题思路 - 原地反转链表
为了满足空间复杂度 O ( 1 ) O(1) O(1) 的要求,我们使用三个指针实现链表的 原地反转:
步骤
-
初始化
prev:指向当前节点的前驱节点(初始为NULL)。cur:指向当前节点。next:临时保存当前节点的后继节点。
-
反转过程
- 逐一将当前节点的
next指针指向prev。 - 将
prev和cur向后移动。
- 逐一将当前节点的
-
结束条件
- 当
cur遍历到链表尾部(即cur ->next== NULL),同时别忘了,把最后一个结点也给处理了,cur->next=pre。链表反转完成,此时cur即为新链表头。
- 当
C语言代码实现
/*** struct ListNode {* int val;* struct ListNode *next;* };*/
/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param head ListNode类 * @return ListNode类*/
struct ListNode* ReverseList(struct ListNode* head ) {if(head==NULL)return head;struct ListNode* cur=head;struct ListNode* pre=NULL;struct ListNode* next=cur->next;while(cur->next!=NULL){cur->next=pre;pre=cur;cur=next;next=cur->next;}cur->next=pre;return cur;// write code here
}
轻松拿捏。
相关文章:
每日一题:BM1 反转链表
文章目录 [toc]问题描述数据范围示例 C代码实现使用栈实现(不符合要求,仅作为思路) 解题思路 - 原地反转链表步骤 C语言代码实现 以前只用过C刷过代码题目,现在试着用C语言刷下 问题描述 给定一个单链表的头结点 pHeadÿ…...
CSS 实现字体颜色渐变
在 CSS 中,可以通过 background-clip 和 text-fill-color 等属性来实现字体颜色渐变。以下是实现字体颜色渐变的基本步骤和示例代码: 示例代码 <!DOCTYPE html><html lang"en"><head><meta charset"UTF-8" /&…...
【软考网工笔记】计算机基础理论与安全——网络安全
病毒 Melissa 宏病毒 1. 是一种快速传播的能够感染那些使用MS Word 97 和MS Office 2000 的计算机宏病毒。 2. 前面有**Macro** 表示这是宏病毒; 3. 宏病毒可以感染后缀为.xls的文件;Worm 蠕虫病毒 1. 通常是通过网络或者系统漏洞进行传播。 2. 利用信…...
JS数组转字符串(3种方法)
JavaScript 允许数组与字符串之间相互转换。其中 Array 方法对象定义了 3 个方法,可以把数组转换为字符串,如表所示。 Array 对象的数组与字符串相互转换方法 数组方法 说明 toString() 将数组转换成一个字符串 toLocalString() 把数组转换成本地约定的…...
云计算安全需求分析与安全防护工程
23.1 概念与威胁分析 1)概念 在传统计算环境下,用户构建一个新的应用系统,需要做大量繁杂的工作,如采购硬件设备、安装软件包、编写软件,同时计算资源与业务发展难以灵活匹配,信息系统项目建设周期长。随…...
C/C++的printf会调用malloc()
排查内存问题(或相关的疑难杂症)时,可能一句printf就能让bug出现,或者赶走bug。你可能觉得很神奇,但这并不神奇。 至少我们可以在 Linux-x64 下,通过 malloc hook,来验证当前的编译环境下&…...
spring mvc源码学习笔记之五
pom.xml 内容如下 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache.org/P…...
3272 小蓝的漆房
将devc设置支持编译就能用新的遍历方式 for(auto &x : s)//遍历容器s,变量为x /* 多循环的嵌套: 计数是否需要重置为0; 是否因为ans定义成全局变量导致ans在比较多时候会出现错误*/ /* 1.对于一个标准色,对目标数组遍历, 如…...
MySQL使用触发器进行备份
触发器脚本备份 实现方案: 1.配置mysql调用外部脚本的插件mysqludf 链接:https://pan.baidu.com/s/1MCrf1u_SRWwcZoxM9JDNiw 提取码:kgt0 解压 2.解压后放进: mysql安装路径/lib/plugin/ 3.在mysql执行命令创建自定义函数&…...
数据结构与算法-顺序表
数据结构 顺序表 基本概念 顺序表:顺序存储的线性表链式表:链式存储的线性表,简称链表 顺序存储就是将数据存储到一片连续的内存中,在C语言环境下,可以是具名的栈数组,也可以是匿名的堆数组。 存储方式…...
OpenAI CEO 奥特曼发长文《反思》
OpenAI CEO 奥特曼发长文《反思》 --- 引言:从 ChatGPT 到 AGI 的探索 ChatGPT 诞生仅一个多月,如今我们已经过渡到可以进行复杂推理的下一代模型。新年让人们陷入反思,我想分享一些个人想法,谈谈它迄今为止的发展,…...
Shell编程详解
文章目录 一、Linux系统结构二、Shell介绍1、Shell简介2、Shell种类3、Shell查询和切换 三、Shell基础语法1、注释2、本地变量3、环境变量3.1、查看环境变量3.2、临时设置环境变量3.3、永久设置环境变量 4、特殊变量5、控制语句5.1、shell中的中括号5.2、if语句5.3、for循环5.4…...
跨站脚本攻击(XSS)详解
跨站脚本攻击(XSS)详解 跨站脚本攻击(XSS,Cross-Site Scripting)是一种通过在网页中注入恶意脚本,攻击用户浏览器的漏洞。攻击者可以利用XSS窃取用户敏感信息、劫持会话、或在受害者浏览器中执行恶意操作。…...
03-QT中的QMainWindow+对话框QDialog
文章目录 1.QMainWindow1.1菜单栏1.2 工具栏1.3 状态栏1.4 铆接部件1.5 核心部件(中心部件)1.6 资源文件 2.对话框2.1 基本概念2.2 标准对话框2.3 自定义消息框2.4 消息对话框2.5 标准文件对话框 1.QMainWindow QMainWindow是一个为用户提供主窗口程序的…...
c# 中Parallel.ForEach 对其中一个变量进行赋值 引发报错
在 C# 中使用 Parallel.ForEach 方法时,如果你尝试在并行循环中对共享变量进行赋值,很可能会遇到线程安全问题或竞争条件(race conditions),这可能导致数据不一致、程序崩溃或其他不可预测的行为。 问题描述 假设你有…...
ElasticSearch备考 -- 整体脉络梳理
1、 search 、Update、reindex ElasticSearch 备考 -- 查询&高亮&排序 ElasticSearch 备考 -- 聚合查询 ElasticSearch 备考 -- 异步检索 2、search temple ElasticSearch备考 -- Search template 3、custom analyzer ElasticSearch 备考 -- 自定义分词 2、…...
vue Element Ui Upload 上传 点击一个按钮,选择多个文件后直接上传,使用防抖解决多次上传的问题。
问题: 在使用Element Ui Upload 上传文件时,选择多个文件上传时,on-change事件会一个一个返回上传的文件,导致前端不知道什么时候可以拿到全部上传的文件,再一起调后台接口。 解决方法: 上传文件后&…...
【HF设计模式】05-单例模式
声明:仅为个人学习总结,还请批判性查看,如有不同观点,欢迎交流。 摘要 《Head First设计模式》第5章笔记:结合示例应用和代码,介绍单例模式,包括遇到的问题、采用的解决方案、以及达到的效果。…...
运维人员的Python详细学习路线
以下是一条适合运维人员的Python详细学习路线: 一、基础入门阶段(第1 - 2个月) 环境搭建与基础语法(第1个月) 安装与配置 在运维常用的操作系统(如Linux或Windows)上安装Python。对于Linux系统…...
软件体系结构与设计模式
在软件开发中,软件体系结构和设计模式是两个至关重要的概念。它们帮助开发者设计出易于理解、可扩展、可维护的系统。尽管这两个概念密切相关,但它们分别关注系统的不同方面:软件体系结构关注的是系统整体结构的设计,而设计模式则…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...
MySQL的pymysql操作
本章是MySQL的最后一章,MySQL到此完结,下一站Hadoop!!! 这章很简单,完整代码在最后,详细讲解之前python课程里面也有,感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...
