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

将单链表反转【数据结构练习题】

news 2025/5/17 6:58:59

- 第 98 篇 -
Date: 2025 - 05 - 16
Author: 郑龙浩/仟墨

反转单链表(出现频率非常的高)

文章目录

  • 反转单链表(出现频率非常的高)
    • 题目：反转一个链表
    • 思路：
    • 代码实现(第3种思路):

题目：反转一个链表

将 1->2->3->4->5->NULL反转变为 5->4->3->2->1->NULL

思路：

三种思路

  • 新建一个新的链表，不断头插
  • 利用递归
  • 将NULL放到1的前边，然后再将指向反转（比如先NULL<-1->2->3->4->5再 NULL<-1<-2->3->4->5，直到NULL<-1<-2<-3<-4<-5）

代码实现(第3种思路):

  • test.c

    // 反转链表
#define _CRT_SECURE_NO_WARNINGS
#include "SListNode.h"
// 反转链表
void reversal(SListNode** pphead, int len) {// 三个 “指针”，分别指向三个连着的结点   初始如下：SListNode *previous = NULL, *current = *pphead, *next = (*pphead)->next;// 情况：1 无结点或只有一个结点 2有大于1个的结点 // 无结点 / 只有一个结点 就直接退出if (current == NULL || next == NULL) {return;}// 链表反转  while (next != NULL) {next = current->next; // **重要！！** 提前存储current的后驱结点（因为当前结点指向前原-来的前驱结点以后，当前结点会丢失原来的后驱结点，也就是原后驱结点的地址会丢失，所以要提前储存，当前结点指向前驱结点以后，让next指针存储）current->next = previous; // 当前结点指向前一个结点// 指针向后移previous = current;current = next;}*pphead = previous; // 头节点指向原来的最后一个结点
}
int main(void) {SListNode* L = NULL;int len = 0; // 链表长度printf("请输入链表的内容:\n");scanf("%d", &len);// 插入 链表内容for (int i = 1; i <= len; i++) {ElemType n;scanf("%d", &n);SListPushBack(&L, n);}SListPrint(L); // 打印链表// 反转链表reversal(&L, len);SListPrint(L);return 0;
}

  • SListNode.c

    #define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"
#include "SListNode.h"
#include "stdlib.h"
SListNode* BuySListNode(ElemType x) {// 申请一个新的结点SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode)); // 为新节点申请内存空间// 养成习惯：判断申请内存是否成功  虽然大概是成功的，但是还是要养成这个习惯if (NewNode == NULL) {printf("申请内存失败!\n");exit(-1);}NewNode->data = x; // 新节点 存入数据xNewNode->next = NULL; // 新节点 指向NULL（初始化），避免越界访问到其他地址return NewNode;
}
// 打印
void SListPrint(SListNode* phead) {SListNode* current = phead; // 当前结点的“地址”while (current != NULL) {printf("%d -> ", current->data); // 打印当前结点中的‘data’current = current->next; // 指向下一个“结点”}printf("NULL\n");
}
// 获取链表宽度（结点数量）
size_t SlistSize(SListNode* phead) {size_t len = 0; // 长度初始化为0SListNode* current = phead; // 遍历链表while (current != NULL) { // 当前节点不为空时计数len++; // 结点数量++current = current->next; // 当前结点指向下一个结点}return len; // 返回链表长度
}
// 头插
void SListPushFront(SListNode** pphead, ElemType x) {SListNode* NewNode = BuySListNode(x); // 创建新的结点NewNode->next = *pphead; // 让新的结点指向“原来的第一个结点”*pphead = NewNode; // 让存放第一个结点地址的*pphead变成存放新结点的地址，也就是让第一个结点变为新的结点 NewNode
}
// 头删
void SListPopFront(SListNode** pphead) {// 三种情况： 1 链表为空 2 链表只有一个结点 3 链表有大于1个的结点if (*pphead == NULL) { // 链表为空，表示无任何结点，则不进行删除操作return;}else if ((*pphead)->next == NULL) { // 链表只有一个结点free(*pphead); // 释放第一个结点的内存空间，将内存还给操作系统*pphead = NULL; // *pphead = NULL; // 将头指针置空，避免指向已释放的内存（野指针）}else {SListNode* next = (*pphead)->next; // 保护第二个结点，避免释放第一个结点内存后找不到第二个结点free(*pphead); // 释放第一个结点*pphead = next; // 让头指针指向第二个结点}
}
// 尾插
void SListPushBack(SListNode** pphead, ElemType x) {SListNode* NewNode = BuySListNode(x); // 先开辟一个新的结点// 判断第一个结点是否为空，若为空，则开辟空间（也就是该链表没有任何数据）if (*pphead == NULL) { // 若节点为空*pphead = NewNode; // 让第一个结点指向新的结点}else {// 找到最后一个结点SListNode* tail = *pphead; // tail 翻译：尾// 找尾结点while (tail->next != NULL) { // 只要当前结点指向NULL，就表示没有下一个结点了，就表示了当前结点就是最后一个结点tail = tail->next;}tail->next = NewNode; // 将原链表的最后一个结点指向新的节点}
}
// 尾删
void SListPopBack(SListNode** pphead) {// 三种情况：1 链表为空（头结点指向 NULL，也就是无结点）   2 只有一个结点  3 有 多于 1 个的结点if (*pphead == NULL) {return;}else if ((*pphead)->next == NULL) {free(*pphead); // 释放第一个结点的内存*pphead = NULL; // *pphead = NULL; // 将头指针置空，避免指向已释放的内存（野指针）}else {SListNode* previous = NULL; // taile的前驱结点  最终找到的是倒数第二个结点SListNode* tail = *pphead; //  previous的后驱结点  最终找到的是最后一个结点while (tail->next != NULL) { // 寻找 最后结点previous = tail; // 指向后指针tail = tail->next; // 指向下一个结点}free(tail); // 释放最后一个结点的内存空间previous->next = NULL; // 让倒数第二个结点指向NULL，而非最后一个结点，因为最后一个结点已经是“野指针”}
}
// 查找   返回存放x的结点的地址(一级指针)
SListNode* SListFind(SListNode* phead, ElemType x) {SListNode* current = phead; // 遍历链表while (current != NULL && current->data != x) { // 如果结点非空且当前结点的data不是x，，则找下一个current = current->next; // 找到下一个结点}return current; // current 会有两种情况，一种是存放x的结点，一种是没找到存放NULL空地址
}
// 在pos位置之前插入x
void SListInsert(SListNode** pphead, SListNode* pos, ElemType x) {// 1 pos 是否合法 2 pos 是否指向第一个结点 3 pos 指向第一个以后的结点if (pos == NULL) { // 地址不对printf("pos地址为空地址，不合法\n");return;}if (*pphead == pos) { // pos 指向第一个结点SListPushFront(pphead, x);  // 直接尾插一个xreturn;}SListNode* previous = *pphead; // pos// 找到前驱结点while (previous != NULL && previous->next != pos) {previous = previous->next; // 指向下一个结点} // previous 在退出循环的时候的两种情况：1 找到前驱 2 没找到，存NULL指针// 插入xif (previous != NULL) { // 找到了SListNode* NewNode = BuySListNode(x); // 申请一个新的结点NewNode->next = pos; // 新的结点指向 pos 结点previous->next = NewNode; // pos的前驱结点指向新的结点}else {printf("没找到！\n");return;}
}
// 删除pos位置的值
void SListErase(SListNode** pphead, SListNode* pos) {// 情况：1 链表为空且pos指向第一个结点 2 pos 是否合法 3 pos 是否指向第一个结点 4 pos 指向第一个以后的结点 if (*pphead == NULL && pos == *pphead) { // 若没结点 且 pos 指向空则不删除return;}// 如果pos指向空，则结点的地址不合法if (pos == NULL) {printf("pos地址为空，不合法！");return;}// 如果pos指向第一个结点if (pos == *pphead) {SListPopFront(pphead); // 直接头删return;}SListNode* previous = *pphead; // pos 的前驱结点// 找到 pos 的前驱结点while (previous != NULL && previous->next != pos) {previous = previous->next; // 指向下一个结点}if (previous == NULL) {printf("未找到要删除的结点\n");return;}previous->next = pos->next; // 让 pos 前驱节点指向 pos 的后驱结点free(pos); // 释放pos结点的内存空间
}
// pos 后面插入的话就无需知道pos前一个结点了，也就无需传输“第一个结点的地址去查找pos前一个结点了”
void SListInsertAfter(SListNode* pos, ElemType x) {if (pos == NULL) {printf("第一个参数错误，pos的地址为空地址NULL！");return;}SListNode* NewNode = BuySListNode(x); // 申请一个新的结点NewNode->next = pos->next; // 让新结点指向原pos的后驱结点pos->next = NewNode; // 让 pos 指向新的结点
}void SListEraseAfter(SListNode* pos) {// 如果pos地址为空if (pos == NULL || pos->next == NULL) {printf("参数错误：pos为空或没有后继节点\n");return;}SListNode* toDelete = pos->next;  // 保存待删除节点(保护删除结点的指针不被丢失)pos->next = toDelete->next;      // pos指向删除结点后边的结点free(toDelete);                   // 释放内存空间
}

  • SListNode.h

    #pragma once
#include "stdio.h"
#include "SListNode.h"
#include "stdlib.h"
typedef int ElemType; // 将 int 重命名为 ElemType，element意思元素
// 单链表结点
typedef struct SListNode {int data;                   // 数据域struct SListNode* next;     // 指针域（指向下一个节点）
} SListNode;
// 动态申请一个新的结点  因为插入当中申请新结点的代码太多了，为了避免冗余代码，将重复代码部分重新封装成了一个新的函数
SListNode* BuySListNode(ElemType x);
// 打印
void SListPrint(SListNode* phead);
// 获取链表宽度（结点数量）
size_t SlistSize(SListNode* phead);
// 头插
void SListPushFront(SListNode** pphead, ElemType x);
// 头删
void SListPopBack(SListNode** pphead);
// 尾插
void SListPushBack(SListNode** pphead, ElemType x);
// 尾删
void SListPopBack(SListNode** pphead);
// 查找
SListNode* SListFind(SListNode* phead, ElemType x);
// 在pos位置之前插入x
void SListInsert(SListNode** pphead, SListNode* pos, ElemType x);
// 删除pos位置的值
void SListErase(SListNode** pphead, SListNode* pos);
// 在pos位置之后插入x
void SListInsertAfter(SListNode* pos, ElemType x);
// 删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
http://www.xdnf.cn/news/483661.html

相关文章：

  • 机器学习入门之KNN算法和交叉验证与超参数搜索（三）
  • 如何在一台环境中同时安装ragflow和ragflow-plus
  • PCL 绘制二次曲面
  • Golang基于反射的ioctl实现
  • 鸿蒙5.0项目开发——鸿蒙天气项目的实现（主页2）
  • HarmonyOS 开发之 —— 合理使用动画与转场
  • userfaultfd内核线程D状态问题排查
  • 数学实验（Matlab编程基础）
  • Flutter - 集成三方库:日志(logger)
  • 【深度学习】#11 优化算法
  • 麒麟服务器操作系统安装 MySQL 8 实战指南
  • EC800X_DP-DTU-Q600R 系列开发板介绍
  • QML 动画控制、顺序动画与并行动画
  • 25考研经验贴（11408）
  • 智能呼叫系统中的NLP意图理解：核心技术解析与实战
  • 游戏引擎学习第286天:开始解耦实体行为
  • R1 快开门式压力容器操作证备考练习题及答案
  • 2025程序设计天梯赛补题报告
  • 《数字藏品APP开发：解锁高效用户身份认证与KYC流程》
  • xss-labs靶场第11-14关基础详解
  • 2025认证杯数学建模第二阶段A题完整论文（代码齐全）:小行星轨迹预测思路
  • MySQL的 JOIN 优化终极指南
  • RAG-MCP：突破大模型工具调用瓶颈，告别Prompt膨胀
  • Android Studio AI插件与Bolt工具实战指南：从零到一打造智能应用
  • PostgreSQL中的全页写
  • 【python编程从入门到到实践】第十章 文件和异常
  • Spring框架（三）
  • 7.重建大师点云处理教程
  • 每周靶点：PCSK9、Siglec15及文献分享
  • python基础语法（三-中）