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

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

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

题目：反转一个链表

将 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);