链表基础3——单链表的逆置
链表的定义
#include <stdio.h>
#include <stdlib.h> typedef struct Node { int data; struct Node* next;
} Node; Node* createNode(int data) { Node* newNode = (Node*)malloc(sizeof(Node)); if (!newNode) { return NULL; } newNode->data = data; newNode->next = NULL; return newNode;
} void printList(Node* head) { Node* current = head; while (current != NULL) { printf("%d ", current->data); current = current->next; } printf("\n");
}
不带头结点的单向不循环链表的逆置
不带头结点的单向不循环链表的逆置方式主要有以下几种:
-
迭代法:
这种方法使用一个指针遍历链表,同时使用另一个指针指向当前节点的前一个节点。在遍历过程中,每次都将当前节点的next指针指向前一个节点,从而实现链表的逆置。需要注意的是,在逆置过程中,还需要保存下一个要处理的节点,因为逆置后当前节点的next指针会指向前一个节点,从而失去对下一个节点的引用。 -
递归法:
递归法通过递归调用实现链表的逆置。递归的基本思想是:先递归到链表的最后一个节点,然后将该节点的next指针指向它的前一个节点,接着返回前一个节点,继续逆置前面的部分。递归法的好处是代码简洁,但递归深度较大时可能会导致栈溢出。 -
栈辅助法:
这种方法利用栈的后进先出特性来实现链表的逆置。首先将链表中的每个节点依次入栈,然后再依次出栈,并将出栈节点的next指针指向它的前一个出栈节点,从而实现链表的逆置。这种方法需要额外的空间来存储栈中的节点。 -
三指针法:
这种方法使用三个指针,分别指向当前节点、前一个节点和下一个节点。在遍历过程中,先将当前节点的next指针指向前一个节点,然后移动三个指针,继续处理下一个节点。这种方法与迭代法类似,但使用了更多的指针来简化操作。
每种方法都有其特点和适用场景,可以根据具体需求选择合适的方法来实现链表的逆置。在实际应用中,还需要考虑代码的可读性、健壮性和性能等因素。
迭代法
// 迭代法逆置链表
void reverseListIterative(Node** head) { Node* prev = NULL; // prev指向前一个节点,初始化为NULL Node* current = *head; // current指向当前节点,初始化为头节点 while (current != NULL) { Node* next = current->next; // next指向下一个节点 current->next = prev; // 将当前节点的next指针指向前一个节点,实现逆置 prev = current; // 将prev移动到当前节点 current = next; // 将current移动到下一个节点 } *head = prev; // 更新头指针,指向新的头节点(原链表的尾节点)
}
逐步分解







到这里循环就结束了
到这里彻底完成链表的逆置
递归法
// 递归法逆置链表
Node* reverseListRecursive(Node* head) { // 递归终止条件:当前节点为空或当前节点的下一个节点为空 if (head == NULL || head->next == NULL) { return head; } // 递归调用,逆置剩余部分链表,并返回新的头节点 Node* newHead = reverseListRecursive(head->next); // 处理当前节点,将其指向原来的前一个节点,实现逆置 head->next->next = head; head->next = NULL; // 返回新的头节点 return newHead;
}// main 函数和其他辅助函数与迭代法相同
递归的思想是将一个大问题分解为若干个更小的子问题来解决。在链表逆置的场景中,我们可以将问题分解为“逆置除头节点外的剩余链表,并将头节点放到逆置后链表的尾部”。
递归函数reverseListRecursive的工作过程如下:
- 基本情况(递归终止条件):
- 如果链表为空(
head == NULL),或者链表只有一个节点(head->next == NULL),那么链表已经逆置完成(或者说,无需逆置),直接返回当前头节点。
- 如果链表为空(
- 递归步骤:
- 假设当前头节点
head的下一个节点开始的链表部分(即剩余链表)已经通过递归调用reverseListRecursive(head->next)逆置完成,并返回了新的头节点newHead。
- 假设当前头节点
- 处理当前节点:
- 在递归调用返回后,
newHead指向逆置后链表的头节点。此时,我们需要将当前节点head放到逆置后链表的尾部。 - 由于
head->next现在指向逆置后的链表,我们将head->next->next指向head,这样就将head节点添加到了逆置后链表的尾部。 - 然后,我们需要将
head->next设置为NULL,因为head现在是新链表的最后一个节点。
- 在递归调用返回后,
- 返回新头节点:
- 最后,递归函数返回
newHead,即逆置后链表的头节点。
- 最后,递归函数返回
这个过程是一个典型的“自底向上”的递归:我们先递归地逆置剩余部分链表,然后再处理当前节点。递归的每一次调用都处理一个更小的子问题,直到到达基本情况(链表为空或只有一个节点)。
以一个简单的例子来说明:
假设链表为
A -> B -> C -> D。
- 递归调用
reverseListRecursive(D),D没有下一个节点,返回D。- 递归调用
reverseListRecursive(C),它首先递归调用reverseListRecursive(D)得到D,然后将C添加到D的前面,得到D -> C,并返回D作为新头节点。- 递归调用
reverseListRecursive(B),它首先递归调用reverseListRecursive(C)得到D -> C,然后将B添加到D -> C的前面,得到C -> D -> B,并返回C作为新头节点。- 最后,
reverseListRecursive(A)调用reverseListRecursive(B)得到C -> D -> B,然后将A添加到C -> D -> B的前面,得到B -> C -> D -> A,并返回B作为新头节点。最终,
A -> B -> C -> D被逆置为B -> C -> D -> A。
通过这种方式,递归能够逐步地将整个链表逆置。希望这个解释能够更清楚地说明递归是如何实现链表逆置的。
栈辅助法
typedef struct Node { int data; struct Node* next;
} Node; typedef struct Stack { Node* top;
} Stack; void push(Stack* stack, Node* node) { node->next = stack->top; stack->top = node;
} Node* pop(Stack* stack) { if (stack->top == NULL) { return NULL; } Node* node = stack->top; stack->top = stack->top->next; node->next = NULL; // 避免悬挂指针 return node;
} bool isEmpty(Stack* stack) { return stack->top == NULL;
} // 栈辅助法逆置链表
Node* reverseListWithStack(Node* head) { StackNode* stack = createStack(); Node* dummy = createNode(0); // 创建一个哑节点作为新链表的头节点 Node* tail = dummy; // tail指向新链表的尾节点 // 将原链表的节点依次入栈 while (head != NULL) { push(&stack, head); head = head->next; } // 将栈中的节点依次出栈并连接到新链表上 while ((head = pop(&stack)) != NULL) { tail->next = head; tail = head; } // 新链表的尾节点指向NULL tail->next = NULL; // 返回新链表的头节点(哑节点的下一个节点) return dummy->next;
} // 辅助函数和main函数与之前相同
三指针法
// 三指针法逆置链表
Node* reverseListWithThreePointers(Node* head) { if (head == NULL || head->next == NULL) { return head; } Node* prev = NULL; Node* current = head; Node* nextTemp = NULL; while (current != NULL) { nextTemp = current->next; // 保存下一个节点 current->next = prev; // 反转当前节点的指针 prev = current; // prev移动到当前节点 current = nextTemp; // current移动到下一个节点 } return prev; // prev现在指向新的头节点
} // ...(其他函数和main函数保持不变)
逐步分解









测验代码
int main() { Node* head = createNode(1); head->next = createNode(2); head->next->next = createNode(3); head->next->next->next = createNode(4); printf("Original List: "); printList(head); reverseListIterative(&head); printf("Reversed List: "); printList(head); // 释放链表内存 Node* temp; while (head != NULL) { temp = head; head = head->next; free(temp); } return 0;
}
带头结点的单向不循环链表的逆置
对于带头结点的单向不循环链表的逆置,我们依然可以使用递归或迭代的方法。
由于头结点通常不存储数据,而是作为链表的起始标识和方便操作,逆置链表时通常不会涉及头结点的变动。
以下,我将分别解释递归和迭代如何对带头结点的单向不循环链表进行逆置。
递归法
在递归法中,我们关注的是链表的当前节点和它的下一个节点。递归的基本思想是:先递归处理子问题(逆置剩余链表),然后处理当前节点。
typedef struct ListNode { int val; struct ListNode *next; } ListNode; ListNode* reverseListRecursive(ListNode* head) { // 如果链表为空或只有一个节点(即头结点后面没有节点),则无需逆置 if (head == NULL || head->next == NULL) { return head; } // 递归调用,逆置头结点后面的链表部分,并返回新的头节点 ListNode* newHead = reverseListRecursive(head->next); // 处理当前头结点,将其next指针指向它的前一个节点 head->next->next = head; // 将当前头结点的next指针置为NULL,因为它现在是新链表的最后一个节点 head->next = NULL; // 返回新的头节点 return newHead; }
在上面的代码中,递归函数reverseListRecursive接收一个指向头结点的指针head,并返回逆置后链表的新的头结点。注意,由于带头结点,我们不会改变头结点的位置,只会改变头结点后面链表的逆置。
迭代法
迭代法则是通过循环和指针操作来逐步逆置链表。对于带头结点的链表,迭代法通常更加直观和易于理解。
ListNode* reverseListIterative(ListNode* head) { if (head == NULL || head->next == NULL) { return head; } ListNode* prev = head; // prev初始指向头结点 ListNode* curr = head->next; // curr初始指向头结点后的第一个节点 // 当curr不为空时,持续进行逆置操作 while (curr != NULL) { ListNode* nextTemp = curr->next; // 保存curr的下一个节点 curr->next = prev; // 将curr的next指针指向前一个节点,实现逆置 prev = curr; // prev向后移动一位 curr = nextTemp; // curr向后移动一位 } // 最后将头结点的next指向新的头节点 head->next = prev; // 返回新的头节点 return prev; }
在这个迭代法中,我们使用三个指针:prev始终指向当前逆置部分的最后一个节点,curr指向待逆置的当前节点,nextTemp用于临时存储curr的下一个节点,以便在逆置当前节点后能够继续迭代。
无论是递归还是迭代法,带头结点的单向不循环链表的逆置操作的关键都在于逐步改变节点的next指针的指向,从而实现链表的逆置。
迭代法通常比递归法在空间效率上更优,因为它不需要递归调用栈的空间。而在时间效率上,两者在平均和最坏情况下通常都是O(n),其中n是链表的长度。
相关文章:
链表基础3——单链表的逆置
链表的定义 #include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node* next; } Node; Node* createNode(int data) { Node* newNode (Node*)malloc(sizeof(Node)); if (!newNode) { return NULL; } newNode->data …...
Fiddler:网络调试利器
目录 第1章:Fiddler简介和安装 1.1 Fiddler概述 1.2 Fiddler的安装步骤 步骤1:下载Fiddler 步骤2:运行安装程序 步骤3:启动Fiddler 1.3 配置Fiddler代理 配置操作系统代理 配置浏览器代理 Google Chrome Mozilla Firefox 第2章:Fiddler界面和基本操作 2.1 Fi…...
【笔记】mysql版本6以上时区问题
前言 最近在项目中发现数据库某个表的createTime字段的时间比中国时间少了13个小时,只是在数据库中查看显示时间不对,但是在页面,又是正常显示中国时区的时间。 排查 项目中数据库的驱动使用的是8.0.19,驱动类使用的是com.mysq…...
Scala实战:打印九九表
本次实战的目标是使用不同的方法实现打印九九表的功能。我们将通过四种不同的方法来实现这个目标,并在day02子包中创建相应的对象。 方法一:双重循环 我们将使用双重循环来实现九九表的打印。在NineNineTable01对象中,我们使用两个嵌套的fo…...
Excel文件解析
在此模块的学习中,我们需要一个新的开源类库---Apahche POI开源类库。这个类库的用途是:解析并生成Excel文件(Word、ppt)。Apahche POI基于DOM方式进行解析,将文件直接加载到内存,所以速度比较快,适合Excel文件数据量不…...
纯css实现switch开关
代码比较简单,有需要直接在下边粘贴使用吧~ html: <div class"switch-box"><input id"switch" type"checkbox"><label></label></div> css: .switch-box {position: relative;height: 25px…...
Unity3d 微信小游戏 AB资源问题
简介 最近在做微信小游戏,因为对unity比较熟悉,而且微信也支持了用unity3d直接导出到小游戏的工具,所以就记录下这期间遇到的问题 微信小游戏启动时间主要受以下三点影响: 下载小游戏首包数据文件下载和编译wasm代码引擎初始化…...
Leetcode二叉树刷题
给你一个二叉树的根节点 root , 检查它是否轴对称。 示例 1: 输入:root [1,2,2,3,4,4,3] 输出:true public boolean isSymmetric(TreeNode root) {if(rootnull)return true;return compare(root.left,root.right);}public boole…...
如何给自己的网站添加 https ssl 证书
文章目录 一、简介二、申请 ssl 证书三、下载 ssl 证书四、配置 nginx五、开放 443 端口六、常见问题解决(一)、配置后,访问 https 无法连接成功(二) 证书配置成功,但是访问 https 还是报不安全 总结参考资料 一、简介 相信大家都知道 https 是更加安全…...
Vue路由跳转及路由传参
跳转 跳转使用 router vue 的路由跳转有 3 个方法: go 、 push 、 replace go :接收数字, 0 刷新,正数前进,负数后退 push :添加,向页面栈中添加一条记录,可以后退 replace &#…...
计算机网络常见面试总结
文章目录 1. 计算机网络基础1.1 网络分层模型1. OSI 七层模型是什么?每一层的作用是什么?2.TCP/IP 四层模型是什么?每一层的作用是什么?3. 为什么网络要分层? 1.2 常见网络协议1. 应用层有哪些常见的协议?2…...
时隔一年,再次讨论下AutoGPT-安装篇
AutoGPT是23年3月份推出的,距今已经1年多的时间了。刚推出时,我们还只能通过命令行使用AutoGPT的能力,但现在,我们不仅可以基于AutoGPT创建自己的Agent,我们还可以通过Web页面与我们创建的Agent进行聊天。这次的AutoGP…...
项目三:学会如何使用python爬虫请求库(小白入门级)
根据上一篇文章我们学会的如何使用请求库和编写请求函数,这一次我们来学习一下爬虫常用的小技巧。 自定义Headers Headers是请求的一部分,包含了关于请求的元信息。我们可以在requests调用中传递一个字典来自定义Headers。代码如下 import requests h…...
【热门话题】PyTorch:深度学习领域的强大工具
🌈个人主页: 鑫宝Code 🔥热门专栏: 闲话杂谈| 炫酷HTML | JavaScript基础 💫个人格言: "如无必要,勿增实体" 文章目录 PyTorch:深度学习领域的强大工具一、PyTorch概述二、PyTorch核心特性…...
SQL注入sqli_libs靶场第一题
第一题 联合查询 1)思路: 有回显值 1.判断有无注入点 2.猜解列名数量 3.判断回显点 4.利用注入点进行信息收集 爆用户权限,爆库,爆版本号 爆表,爆列,爆账号密码 2)解题过程࿱…...
QT_day3
完善对话框,点击登录对话框,如果账号和密码匹配,则弹出信息对话框,给出提示”登录成功“,提供一个Ok按钮,用户点击Ok后,关闭登录界面,跳转到其他界面 如果账号和密码不匹配…...
使用ADO.NET访问数据库
目录 访问数据库的步骤 1、建立数据库 2、设置链接参数 (1)web网页和数据库连接的方法一 (2)web网页和数据库连接的方法二 3、建立链接对象 4、显示数据库 5、数…...
SpringBoot的旅游管理系统+论文+ppt+免费远程调试
项目介绍: 基于SpringBoot旅游网站 旅游管理系统 本旅游管理系统采用的数据库是Mysql,使用SpringBoot框架开发。在设计过程中,充分保证了系统代码的良好可读性、实用性、易扩展性、通用性、便于后期维护、操作方便以及页面简洁等特点。 (1&…...
数据结构---线性表
1,顺序表实现---动态分配 #include<stdlib.h> #define InitSize 10 typedef struct {int *data;//静态分配int length;int MaxSize; }SqList; void InitList(SqList& L) {L.data (int*)malloc(InitSize * sizeof(int));//分配空间L.length 0;L.MaxSize…...
MySQL 8.0 字符集问题导致报错
报错: ### Error querying database. Cause: java.sql.SQLException: Illegal mix of collations (utf8_general_ci,IMPLICIT) and (utf8mb4_0900_ai_ci,COERCIBLE) MySQL 8.0引入了一些新的字符集和排序规则,并对现有的进行了改进。在MySQL 8.0中&#…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
【VLNs篇】07:NavRL—在动态环境中学习安全飞行
项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战,克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...
处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...
