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

链表基础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");  
}  

不带头结点的单向不循环链表的逆置

不带头结点的单向不循环链表的逆置方式主要有以下几种:

  1. 迭代法
    这种方法使用一个指针遍历链表,同时使用另一个指针指向当前节点的前一个节点。在遍历过程中,每次都将当前节点的next指针指向前一个节点,从而实现链表的逆置。需要注意的是,在逆置过程中,还需要保存下一个要处理的节点,因为逆置后当前节点的next指针会指向前一个节点,从而失去对下一个节点的引用。

  2. 递归法
    递归法通过递归调用实现链表的逆置。递归的基本思想是:先递归到链表的最后一个节点,然后将该节点的next指针指向它的前一个节点,接着返回前一个节点,继续逆置前面的部分。递归法的好处是代码简洁,但递归深度较大时可能会导致栈溢出。

  3. 栈辅助法
    这种方法利用栈的后进先出特性来实现链表的逆置。首先将链表中的每个节点依次入栈,然后再依次出栈,并将出栈节点的next指针指向它的前一个出栈节点,从而实现链表的逆置。这种方法需要额外的空间来存储栈中的节点。

  4. 三指针法
    这种方法使用三个指针,分别指向当前节点、前一个节点和下一个节点。在遍历过程中,先将当前节点的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的工作过程如下:

  1. 基本情况(递归终止条件)
    • 如果链表为空(head == NULL),或者链表只有一个节点(head->next == NULL),那么链表已经逆置完成(或者说,无需逆置),直接返回当前头节点。
  2. 递归步骤
    • 假设当前头节点head的下一个节点开始的链表部分(即剩余链表)已经通过递归调用reverseListRecursive(head->next)逆置完成,并返回了新的头节点newHead
  3. 处理当前节点
    • 在递归调用返回后,newHead指向逆置后链表的头节点。此时,我们需要将当前节点head放到逆置后链表的尾部。
    • 由于head->next现在指向逆置后的链表,我们将head->next->next指向head,这样就将head节点添加到了逆置后链表的尾部。
    • 然后,我们需要将head->next设置为NULL,因为head现在是新链表的最后一个节点。
  4. 返回新头节点
    • 最后,递归函数返回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个小时&#xff0c;只是在数据库中查看显示时间不对&#xff0c;但是在页面&#xff0c;又是正常显示中国时区的时间。 排查 项目中数据库的驱动使用的是8.0.19&#xff0c;驱动类使用的是com.mysq…...

Scala实战:打印九九表

本次实战的目标是使用不同的方法实现打印九九表的功能。我们将通过四种不同的方法来实现这个目标&#xff0c;并在day02子包中创建相应的对象。 方法一&#xff1a;双重循环 我们将使用双重循环来实现九九表的打印。在NineNineTable01对象中&#xff0c;我们使用两个嵌套的fo…...

Excel文件解析

在此模块的学习中&#xff0c;我们需要一个新的开源类库---Apahche POI开源类库。这个类库的用途是&#xff1a;解析并生成Excel文件(Word、ppt)。Apahche POI基于DOM方式进行解析&#xff0c;将文件直接加载到内存&#xff0c;所以速度比较快&#xff0c;适合Excel文件数据量不…...

纯css实现switch开关

代码比较简单&#xff0c;有需要直接在下边粘贴使用吧~ html: <div class"switch-box"><input id"switch" type"checkbox"><label></label></div> css&#xff1a; .switch-box {position: relative;height: 25px…...

Unity3d 微信小游戏 AB资源问题

简介 最近在做微信小游戏&#xff0c;因为对unity比较熟悉&#xff0c;而且微信也支持了用unity3d直接导出到小游戏的工具&#xff0c;所以就记录下这期间遇到的问题 微信小游戏启动时间主要受以下三点影响&#xff1a; 下载小游戏首包数据文件下载和编译wasm代码引擎初始化…...

Leetcode二叉树刷题

给你一个二叉树的根节点 root &#xff0c; 检查它是否轴对称。 示例 1&#xff1a; 输入&#xff1a;root [1,2,2,3,4,4,3] 输出&#xff1a;true public boolean isSymmetric(TreeNode root) {if(rootnull)return true;return compare(root.left,root.right);}public boole…...

如何给自己的网站添加 https ssl 证书

文章目录 一、简介二、申请 ssl 证书三、下载 ssl 证书四、配置 nginx五、开放 443 端口六、常见问题解决(一)、配置后&#xff0c;访问 https 无法连接成功(二) 证书配置成功&#xff0c;但是访问 https 还是报不安全 总结参考资料 一、简介 相信大家都知道 https 是更加安全…...

Vue路由跳转及路由传参

跳转 跳转使用 router vue 的路由跳转有 3 个方法&#xff1a; go 、 push 、 replace go &#xff1a;接收数字&#xff0c; 0 刷新&#xff0c;正数前进&#xff0c;负数后退 push &#xff1a;添加&#xff0c;向页面栈中添加一条记录&#xff0c;可以后退 replace &#…...

计算机网络常见面试总结

文章目录 1. 计算机网络基础1.1 网络分层模型1. OSI 七层模型是什么&#xff1f;每一层的作用是什么&#xff1f;2.TCP/IP 四层模型是什么&#xff1f;每一层的作用是什么&#xff1f;3. 为什么网络要分层&#xff1f; 1.2 常见网络协议1. 应用层有哪些常见的协议&#xff1f;2…...

时隔一年,再次讨论下AutoGPT-安装篇

AutoGPT是23年3月份推出的&#xff0c;距今已经1年多的时间了。刚推出时&#xff0c;我们还只能通过命令行使用AutoGPT的能力&#xff0c;但现在&#xff0c;我们不仅可以基于AutoGPT创建自己的Agent&#xff0c;我们还可以通过Web页面与我们创建的Agent进行聊天。这次的AutoGP…...

项目三:学会如何使用python爬虫请求库(小白入门级)

根据上一篇文章我们学会的如何使用请求库和编写请求函数&#xff0c;这一次我们来学习一下爬虫常用的小技巧。 自定义Headers Headers是请求的一部分&#xff0c;包含了关于请求的元信息。我们可以在requests调用中传递一个字典来自定义Headers。代码如下 import requests h…...

【热门话题】PyTorch:深度学习领域的强大工具

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 PyTorch&#xff1a;深度学习领域的强大工具一、PyTorch概述二、PyTorch核心特性…...

SQL注入sqli_libs靶场第一题

第一题 联合查询 1&#xff09;思路&#xff1a; 有回显值 1.判断有无注入点 2.猜解列名数量 3.判断回显点 4.利用注入点进行信息收集 爆用户权限&#xff0c;爆库&#xff0c;爆版本号 爆表&#xff0c;爆列&#xff0c;爆账号密码 2&#xff09;解题过程&#xff1…...

QT_day3

完善对话框&#xff0c;点击登录对话框&#xff0c;如果账号和密码匹配&#xff0c;则弹出信息对话框&#xff0c;给出提示”登录成功“&#xff0c;提供一个Ok按钮&#xff0c;用户点击Ok后&#xff0c;关闭登录界面&#xff0c;跳转到其他界面 如果账号和密码不匹配&#xf…...

使用ADO.NET访问数据库

目录 访问数据库的步骤 &#xff11;、建立数据库 &#xff12;、设置链接参数 &#xff08;1&#xff09;web网页和数据库连接的方法一 &#xff08;2&#xff09;web网页和数据库连接的方法二 &#xff13;、建立链接对象 &#xff14;、显示数据库 &#xff15;、数…...

SpringBoot的旅游管理系统+论文+ppt+免费远程调试

项目介绍: 基于SpringBoot旅游网站 旅游管理系统 本旅游管理系统采用的数据库是Mysql&#xff0c;使用SpringBoot框架开发。在设计过程中&#xff0c;充分保证了系统代码的良好可读性、实用性、易扩展性、通用性、便于后期维护、操作方便以及页面简洁等特点。 &#xff08;1&…...

数据结构---线性表

1&#xff0c;顺序表实现---动态分配 #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 字符集问题导致报错

报错&#xff1a; ### Error querying database. Cause: java.sql.SQLException: Illegal mix of collations (utf8_general_ci,IMPLICIT) and (utf8mb4_0900_ai_ci,COERCIBLE) MySQL 8.0引入了一些新的字符集和排序规则&#xff0c;并对现有的进行了改进。在MySQL 8.0中&#…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...