线性表的反转 傷城~ 2022-12-24 14:50 66阅读 0赞 线性表的反转，是指将头结点变成尾结点，尾结点变成头结点 这个主要注意两点：防止断链，所以要提前保留当前指针的后一个指针，当前指针的next域要，指向前一个结点，所以要有前一个结点的指针，再加上当前结点，就是 共有三个辅助指针变量。 不多说，直接上代码，这里的代码用到了之前的我的一篇文章里的代码 [线性表的链式存储（传统模式）][Link 1] 话不多说，直接上代码： #include<iostream> #include<vector> using namespace std; struct Node { int data; struct Node*next; }; /*单链表插入操作 带头结点，输入参数：头指针，插入位置，元素值 返回值：插入成功 0，插入失败 -1头指针为空或者位置小于零，-2，插入位置不存在 */ int InsertList(struct Node*pNode, int i, int e) { if (pNode == NULL||i<0) { return -1; } int j = 0;//计数变量 struct Node*cur = pNode;//辅助指针变量 while (cur->next != NULL&&j < i) { cur = cur->next; j++; } if (j>i || cur == NULL) { return -2; } struct Node*newnode = (struct Node*)malloc(sizeof(struct Node)); newnode->data = e; newnode->next = cur->next; cur->next = newnode; return 0; } /*单链表删除操作 带头结点，输入参数：头指针，删除位置，输出参数 元素值 返回值：插入成功 0，删除失败 -1头指针为空或位置小于零，-2，删除位置不存在 */ int DeleteList(struct Node*pNode, int i, int* e) { if (pNode == NULL||i<0) { return -1; } int j = 0;//计数变量 struct Node*cur = pNode;//辅助指针变量 while (cur->next != NULL&&j < i) { cur = cur->next; j++; } if (j>i || cur == NULL) { return -2; } *e = cur->next->data; struct Node*temp = cur->next; cur->next = cur->next->next; free(temp); temp = NULL; return 0; } //初始化一个链表 //输入参数 二级指针 //返回值，分配内存成功返回零，分配失败返回-1 int CreatList(struct Node**head) { struct Node*temp = (struct Node*)malloc(sizeof(struct Node)); if (temp == NULL) { return -1; } temp->data = -1; temp->next = NULL; *head = temp; return 0; } //二叉链表的遍历 //入参 头指针 //返回值 头指针为空返回-1，非空返回0 int TravList(struct Node*head) { if (head == NULL) { return -1; } int i = 0; struct Node*temp = head; while (temp->next != NULL) { printf("list[%d] is [%d]\n", i, temp->next->data); temp = temp->next; i++; } } //销毁整个链表 //输出参数 二级指针 //返回值 -1 传入的头指针为空 0销毁成功 int DestoryList(struct Node**head) { if (*head == NULL) { return -1; } //需要两个辅助指针变量，销毁整个结点前保留下一个结点 struct Node*cur_node = (*head)->next; struct Node*next_node = NULL; while (cur_node != NULL) { next_node = cur_node->next; free(cur_node); cur_node = NULL; cur_node = next_node; } //最后释放头指针 free(*head); *head = NULL; } //单链表的反转 //两中方式 1.把这个链表遍历一遍，然后存储在vector中,然后重新建立一个链表， //这样还要销毁原来的链表，然后重新申请空间创建链表，再进行插入，时间和空间复杂度都挺大 //方式2.空间复杂度o(1) 原地处理，直接修改链表的指针 先处理不带头结点的 void Reverse(struct Node**head) { if (*head == NULL) { return; } struct Node*cur_node = *head; struct Node*next_node=NULL; struct Node*pre_node = NULL; while (cur_node!= NULL) { next_node = cur_node->next; if (next_node == NULL) { *head = cur_node; } cur_node->next = pre_node; pre_node = cur_node; cur_node = next_node; } } int main() { struct Node*head = NULL; if (CreatList(&head) == -1) { printf("malloc failed\n"); } InsertList(head,0,1); InsertList(head,1,2); InsertList(head,2,3); InsertList(head,3,4); TravList(head); Reverse(&head); TravList(head); } 输出结果如下： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5naHVhaWNoYW8_size_16_color_FFFFFF_t_70][] 我们发现反转后，和反转前比较，不是 4 3 2 1，而是 3 2 1 -1，这个是因为我之前写的代码有头结点，然后反转后，把头结点变成了尾结点，然后打印的函数又是默认 不打印第一个结点（认为第一个结点是头结点造成的），重新改下打印函数，如下： #include<iostream> #include<vector> using namespace std; struct Node { int data; struct Node*next; }; /*单链表插入操作 带头结点，输入参数：头指针，插入位置，元素值 返回值：插入成功 0，插入失败 -1头指针为空或者位置小于零，-2，插入位置不存在 */ int InsertList(struct Node*pNode, int i, int e) { if (pNode == NULL||i<0) { return -1; } int j = 0;//计数变量 struct Node*cur = pNode;//辅助指针变量 while (cur->next != NULL&&j < i) { cur = cur->next; j++; } if (j>i || cur == NULL) { return -2; } struct Node*newnode = (struct Node*)malloc(sizeof(struct Node)); newnode->data = e; newnode->next = cur->next; cur->next = newnode; return 0; } /*单链表删除操作 带头结点，输入参数：头指针，删除位置，输出参数 元素值 返回值：插入成功 0，删除失败 -1头指针为空或位置小于零，-2，删除位置不存在 */ int DeleteList(struct Node*pNode, int i, int* e) { if (pNode == NULL||i<0) { return -1; } int j = 0;//计数变量 struct Node*cur = pNode;//辅助指针变量 while (cur->next != NULL&&j < i) { cur = cur->next; j++; } if (j>i || cur == NULL) { return -2; } *e = cur->next->data; struct Node*temp = cur->next; cur->next = cur->next->next; free(temp); temp = NULL; return 0; } //初始化一个链表 //输入参数 二级指针 //返回值，分配内存成功返回零，分配失败返回-1 int CreatList(struct Node**head) { struct Node*temp = (struct Node*)malloc(sizeof(struct Node)); if (temp == NULL) { return -1; } temp->data = -1; temp->next = NULL; *head = temp; return 0; } //二叉链表的遍历 //入参 头指针 //返回值 头指针为空返回-1，非空返回0 int TravList(struct Node*head,bool bInclude_Headnode=true) { if (head == NULL) { return -1; } int i = 0; struct Node*temp = head; if (bInclude_Headnode == true) { while (temp->next != NULL) { printf("list[%d] is [%d]\n", i, temp->next->data); temp = temp->next; i++; } } else { while (temp!= NULL) { printf("list[%d] is [%d]\n", i, temp->data); temp = temp->next; i++; } } } //销毁整个链表 //输出参数 二级指针 //返回值 -1 传入的头指针为空 0销毁成功 int DestoryList(struct Node**head) { if (*head == NULL) { return -1; } //需要两个辅助指针变量，销毁整个结点前保留下一个结点 struct Node*cur_node = (*head)->next; struct Node*next_node = NULL; while (cur_node != NULL) { next_node = cur_node->next; free(cur_node); cur_node = NULL; cur_node = next_node; } //最后释放头指针 free(*head); *head = NULL; } //单链表的反转 //两中方式 1.把这个链表遍历一遍，然后存储在vector中,然后重新建立一个链表， //这样还要销毁原来的链表，然后重新申请空间创建链表，再进行插入，时间和空间复杂度都挺大 //方式2.空间复杂度o(1) 原地处理，直接修改链表的指针 先处理不带头结点的 void Reverse(struct Node**head) { if (*head == NULL) { return; } struct Node*cur_node = *head; struct Node*next_node=NULL; struct Node*pre_node = NULL; while (cur_node!= NULL) { next_node = cur_node->next; if (next_node == NULL) { *head = cur_node; } cur_node->next = pre_node; pre_node = cur_node; cur_node = next_node; } } int main() { struct Node*head = NULL; if (CreatList(&head) == -1) { printf("malloc failed\n"); } InsertList(head,0,1); InsertList(head,1,2); InsertList(head,2,3); InsertList(head,3,4); TravList(head); Reverse(&head); TravList(head,false); } 输出的结果如下： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5naHVhaWNoYW8_size_16_color_FFFFFF_t_70 1][] [Link 1]: https://blog.csdn.net/zhanghuaichao/article/details/108926338 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5naHVhaWNoYW8_size_16_color_FFFFFF_t_70]: /images/20221120/624d11f23bbd40959ea7d314db1c1bce.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5naHVhaWNoYW8_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201128212805878.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5naHVhaWNoYW8=,size_16,color_FFFFFF,t_70
相关 反转链表 > [剑指Offer 24 反转链表 \[easy\] ][Offer 24 _ _easy_] > ![在这里插入图片描述][watermark_type_ZmFuZ3p 曾经终败给现在/ 2022年12月27日 01:21/ 0 赞/ 203 阅读
相关 线性表的反转 线性表的反转，是指将头结点变成尾结点，尾结点变成头结点 这个主要注意两点：防止断链，所以要提前保留当前指针的后一个指针，当前指针的next域要，指向前一个结点，所以要有前一个 傷城~/ 2022年12月24日 14:50/ 0 赞/ 67 阅读
相关 反转链表 / 反转链表 给一条单链表，请反转整个链表，并返回反转后的链表 / public class Test5 { / 这个递归函数的定 àì夳堔傛蜴生んèń/ 2022年10月29日 01:50/ 0 赞/ 221 阅读
相关 反转链表 代码： // by nby \include<iostream> using namespace std; struct node \{ int 以你之姓@/ 2022年08月07日 07:37/ 0 赞/ 219 阅读
相关 链表反转 public class LinkedListReverse { public static void main(String[] args) { ￡神魔★判官ぃ/ 2022年05月24日 08:05/ 0 赞/ 271 阅读
相关 线性表的表元素反转的代码实现（python语言） def reverse(self): 表元素的反转 p = None p指向空 while self.head is not N ゝ一世哀愁。/ 2022年05月24日 03:47/ 0 赞/ 192 阅读
相关 反转链表 题目描述 输入一个链表，反转链表后，输出新链表的表头。 链表的数据结构如下： public class ListNode { int val; 浅浅的花香味﹌/ 2022年05月13日 22:45/ 0 赞/ 278 阅读
相关 反转链表 [反转链表][Link 1] 题目描述 输入一个链表，反转链表后，输出新链表的表头。 1 public class Solution { 心已赠人/ 2022年03月25日 15:26/ 0 赞/ 248 阅读
相关 反转链表 时间限制：1秒 空间限制：32768K 热度指数：408664 本题知识点： 链表 算法知识视频讲解 题目描述 输入一个链表，反转链表后，输出新链表的表头。 妖狐艹你老母/ 2022年03月10日 01:30/ 0 赞/ 262 阅读
相关 链表反转 include "stdafx.h" include<iostream> include<cmath> using namespace 不念不忘少年蓝@/ 2021年09月12日 02:40/ 0 赞/ 417 阅读
曾经终败给现在
傷城~
àì夳堔傛蜴生んèń
￡神魔★判官ぃ
不念不忘少年蓝@
还没有评论，来说两句吧...