当前位置: 首页 > news >正文

反转链表(精美图示详解哦)

全文目录

  • 引言
  • 反转链表
    • 题目描述与思路
    • 实现
  • 总结

引言

在学习了单链表的相关知识后,尝试实现一些题目可以帮助我们更好的理解单链表的结构以及对其的使用。

从这篇文章开始,将会介绍一些编程题来帮助我们更好的掌握单链表:
分别是反转链表、链表的中间结点、链表的倒数第k个结点、合并两个有序链表。

本篇文章将介绍反转链表:

反转链表OJ链接

反转链表

题目描述与思路

在这里插入图片描述
这道题要求我们实现将一个单链表反转。即原来是结点的数据依次为1,2,3,反转后的链表为3,2,1。函数的参数为链表第一个结点的地址。结构体变量与主函数部分已经定义,我们只需要实现接口即可。

之前我们实现过将一个数组的元素反转:
left为首元素的地址;right为尾元素的地址。我们可以通过循环的方式,每次用一个临时变量来帮助我们将left指向的元素与right指向的元素互换,left++、right–,直到left与right相遇时即转换完毕。

//循环例
while (left < right)
{int temp = *right;*right = *left;*left = temp;left++;right--;
}

但是,这样的思路对于反转单链表而言,显然是不能实现的。因为对于单链表而言,想要由最后一个结点访问到倒数第二个结点是不能实现的。

我们直到,链表在存储数据时,只是逻辑上连续,物理空间上是不连续的。
所以我们可以尝试改变单链表的逻辑链接刺绣,从而实现反转链表:

我们可以使链表中,后一个结点的next成员指向前一个链表的地址。将第一个结点的next成员改为NULL,原来指向第一个结点的head指针改为最后一个结点的地址。
这样,就可以实现从head开始,倒着连接单链表。

实现

为了实现上面简述的思路,我们可能需要三个结构体指针:

struct ListNode* beforecur;
struct ListNode* cur;
struct ListNode* aftercur;

cur用于遍历整个链表,beforecur指向cur前面的一个结点。
在每次循环中,我们需要将cur的next成员改为cur前面的结点的指针,即beforecur。
在每次赋值完后,beforecur需要向后移动到下一个结点的位置,将beforecur赋值为cur即可。

但是当cur->next被改变后,cur与其下一个结点的逻辑连接就会断掉,我们就不能访问到cur的下一个结点了。所以,我们需要在cur->next的值改变之前,将其赋给aftercur。这样我们就可以在下一次循环时,将cur赋值为aftercur从而实现cur移动到下一个结点的位置。

同样的,将beforecur赋值为cur需要在cur被改变前:
在这里插入图片描述

循环结束后,我们还需要将head的值改为beforecur,即让head指向单链表的最后一个结点(由于在最后一次循环后,beforecur与cur都已经向后移动过了,beforecur指向的是最后一个结点):
在这里插入图片描述

struct ListNode* reverseList(struct ListNode* head) 
{typedef struct ListNode ListNode;ListNode* beforecur = NULL;ListNode* cur = head;ListNode* aftercur = head;while (aftercur){aftercur = cur->next;cur->next = beforecur;beforecur = cur;cur = aftercur;}head = beforecur;return head;
}

在这里插入图片描述

总结

到此,关于反转链表题目的实现方法已经介绍完了
当然,这只是其中一种方法,相信还有别的思路。欢迎大家在评论区讨论

还有几道关于单链表的题目讲解,欢迎持续关注哦

如果大家认为我对某一部分没有介绍清楚或者某一部分出了问题,欢迎大家在评论区提出

如果本文对你有帮助,希望一键三连哦

希望与大家共同进步哦

相关文章:

反转链表(精美图示详解哦)

全文目录引言反转链表题目描述与思路实现总结引言 在学习了单链表的相关知识后&#xff0c;尝试实现一些题目可以帮助我们更好的理解单链表的结构以及对其的使用。 从这篇文章开始&#xff0c;将会介绍一些编程题来帮助我们更好的掌握单链表&#xff1a; 分别是反转链表、链表…...

深入理解多线程

一、线程基本概念 1、概述 线程是允许应用程序并发的一种机制。线程共享进程内的所有资源。 线程是调度的基本单位。 每个线程都有自己的 errno。 所有 pthread 函数均以返回 0 表示成功&#xff0c;返回一个正值表示失败。 编译 pthread 程序需要添加链接库&#xff08;…...

华为OD机试题 - 英文输入法(JavaScript)

更多题库,搜索引擎搜 梦想橡皮擦华为OD 👑👑👑 更多华为OD题库,搜 梦想橡皮擦 华为OD 👑👑👑 更多华为机考题库,搜 梦想橡皮擦华为OD 👑👑👑 华为OD机试题 最近更新的博客使用说明本篇题解: 英文输入法题目输入输出示例一输入输出说明示例一输入输出Code…...

64 云原生容器化

文章目录 一、什么是rancher二、为什么使用rancher三、 Rancher与[k8s](https://so.csdn.net/so/search?q=k8s&spm=1001.2101.3001.7020)的关系及区别1、Rancher具有的优势三、rancher安装1、细部介绍四、图形化操作1、执行2、图形化操作1、进行客户机登录rancher2、Ranch…...

IronXL for .NET 2023.2.5 Crack

关于适用于 .NET 的 IronXL 在 C# 中阅读和编辑 Excel 电子表格&#xff0c;无需 MS Office 或 Excel Interop。 IronXL for .NET 允许开发人员在 .NET 应用程序和网站中读取、生成和编辑 Excel&#xff08;和其他电子表格文件&#xff09;。您可以读取和编辑 XLS/XLSX/CSV/TS…...

计算机组成原理|第一章(笔记)

目录第一章 计算机系统概论1.1 计算机系统简介1.1.1 计算机的软硬件概念1.1.2 计算机系统的层次结构1.1.3 计算机组成和计算机体系结构1.2 计算机的基本组成1.2.1 冯 诺伊曼计算机的特点1.2.2 计算机的硬件框图1.2.3 计算机的工作过程1.3 计算机硬件的主要技术指标1.3.1 机器字…...

[ vulnhub靶机通关篇 ] Empire Breakout 通关详解

&#x1f36c; 博主介绍 &#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 _PowerShell &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【数据通信】 【通讯安全】 【web安全】【面试分析】 &#x1f389;点赞➕评论➕收藏 养成习…...

IP定位离线库有什么作用?

IP离线是什么意思&#xff1f;我们以丢失手机为例来寻找它&#xff0c;现在手机都有IP定位功能&#xff0c;只要手机开通了IP定位&#xff0c;就能找到手机。iPhone定位显示离线一般是iPhone手机关机了或者iPhone手机中“查找我的iPhone”功能关闭了。如果手机在手中的话可以打…...

[C++]vector模拟实现

目录 前言&#xff1a; 1. vector结构 2. 默认成员函数 2.1 构造函数 无参构造&#xff1a; 有参构造&#xff1a; 有参构造重载&#xff1a; 2.2 赋值运算符重载、拷贝构造&#xff08;难点&#xff09; 2.3 析构函数&#xff1a; 3. 扩容 3.1 reserve 3.2 resize…...

DevOps实战50讲-(2)Jenkins配置

1. Docker镜像方式安装拉取Jenkins镜像docker pull jenkins/jenkins编写docker-compose.ymlversion: "3.1" services:jenkins:image: jenkins/jenkinscontainer_name: jenkinsports:- 8080:8080- 50000:50000volumes:- ./data/:/var/jenkins_home/首次启动会因为数据…...

LC-1599. 经营摩天轮的最大利润(贪心)

1599. 经营摩天轮的最大利润 难度中等39 你正在经营一座摩天轮&#xff0c;该摩天轮共有 4 个座舱 &#xff0c;每个座舱 最多可以容纳 4 位游客 。你可以 逆时针 轮转座舱&#xff0c;但每次轮转都需要支付一定的运行成本 runningCost 。摩天轮每次轮转都恰好转动 1 / 4 周。…...

Umi使用百度地图服务

需求描述 需要在前端页面中使用地图定位功能&#xff0c;所以在前端umi项目中使用百度地图服务&#xff0c;由于umi项目默认没有入口的html文件&#xff0c;所以无法通过常规的在head中加入外链js的方式使用 百度ak zyqeLCzvQPCCNImRu9yRGOqWlEUicxxGreact使用百度api 链接:…...

js中getBoundingClientRect()方法

getBoundingClientRect()返回值是一个 DOMRect 对象&#xff0c;是包含整个元素的最小矩形&#xff08;包括 padding 和 border-width&#xff09;。该对象使用 left、top、right、bottom、x、y、width 和 height 这几个以像素为单位的只读属性描述整个矩形的位置和大小。除了 …...

Unity记录2.2-动作-动画、相机、Debug与总结

文章首发及后续更新&#xff1a;https://mwhls.top/4453.html&#xff0c;无图/无目录/格式错误/更多相关请至首发页查看。 新的更新内容请到mwhls.top查看。 欢迎提出任何疑问及批评&#xff0c;非常感谢&#xff01; 汇总&#xff1a;Unity 记录 摘要&#xff1a;重写了动画触…...

分享十个前端Web3D可视化框架附地址

Three.js&#xff1a;Three.js是一个流行的3D库&#xff0c;提供了大量的3D功能&#xff0c;包括基本几何形状、材质、灯光、动画、特效等。它是一个功能强大、易于使用的框架&#xff0c;广泛用于Web3D可视化应用程序的开发。Three.js&#xff1a;https://threejs.org/Babylon…...

基于WSL2和Clion搭建Win下C开发环境

系列文章目录 一、基于WSL2和Clion搭建Win下C开发环境 二、make、makeFile、CMake、CMakeLists的使用 三、全面、详细、通俗易懂的C语言语法和标准库 文章目录系列文章目录前言WSL2安装WSL常用命令VSCode连接WSLroot密码以systemd启动配置sshClion结语前言 Win下C语言开发环境…...

考研第一天,汤家凤基础班,连续与极限复习笔记

函数连续极限性质保号性证明极值点&#xff1a;夹逼准则二项式展开根号下&#xff0c;大于一&#xff0c;小于一的讨论直接放缩求和分子分母齐次&#xff0c;且分母大一次&#xff0c;用积分单调有界存在极限几个重要的切线放缩证明有界&#xff0c;然后放缩求单调证明有界&…...

聊一聊代码重构——关于变量的代码实践

提炼变量 其目标是将一个复杂表达式或语句分解成更小的部分&#xff0c;并将其存储在变量中。提高代码可读性和复用性 复杂的表达式 有些时候为了方便我们会把业务处理的逻辑写在一起&#xff0c;如果参与处理的内容较多时我们就会创造出一个非常长且难以理解的表达式。当其他…...

Spring之基于注解方式实例化BeanDefinition(1)

最近开始读Spring源码&#xff0c;读着读着发现里面还是有很多很好玩的东西在里面的&#xff0c;里面涉及到了大量的设计模式以及各种PostProcessor注入的过程&#xff0c;很好玩&#xff0c;也很复杂&#xff0c;本文就是记录一下我学习过程中的主干流程。 在开始我们源码解读…...

【STM32】入门(十四):FreeRTOS-任务

1、简述 FreeRTOS应用程序由一组独立的任务构成。 在任何时间点&#xff0c;应用程序中只能执行一个任务&#xff0c;FreeRTOS调度器负责决定所要执行的任务。 每个任务在自己的上下文中执行&#xff0c;不依赖于系统内的其他任务或 FreeRTOS的调度器本身。 FreeRTOS调度器负责…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

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

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

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...