大佬教程收集整理的这篇文章主要介绍了C++数据结构与算法之反转链表的方法详解,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
本文实例讲述了C++数据结构与算法之反转链表的方法。分享给大家供大家参考,具体如下:
算法概述:要求实现将一条单向链表反转并考虑时间复杂度。
算法分析:
数组法(略):
将列表元素逐个保存进数组,之后再逆向重建列表
点评:实现逻辑最简单,需要额外的内存开销。
移动指针:
通过三个指针逐个从链表头开始逐一反转链表元素的指针
点评:不需要额外的内存开销,会改变原始链表。
递归:
以递归的方式首先找到链表尾部,再逐一反转指针
点评:不需要额外的内存开销,不会改变原始链表。
算法实现:
构建链表结构
/* 节点结构 */ struct NODE { int data; struct NODE* next; }; /* 添加元素-压栈 */ voID push(NODE** head,int dat) { struct NODE* new_node = new NODE(); new_node->data = dat; new_node->next = *head; *head = new_node; } /* 添加元素-添加 */ voID add(NODE** head,int dat) { struct NODE* new_node = new NODE(); new_node->data = dat; new_node->next = NulL; if (*head != NulL) { struct NODE* temp = *head; while (temp->next != NulL) { temp = temp->next; } temp->next = new_node; } else { *head = new_node; } }
移动指针
/* 反转列表 */ voID reverse(NODE** head) { struct NODE* pre = NulL; struct NODE* cur = *head; struct NODE* nxt; while (cur != NulL) { // 反转指针 nxt = cur->next; cur->next = pre; // 移动指针 pre = cur; cur = nxt; } *head = pre; }
递归
/* 反转列表-复制原表返回反转表 */ NODE* reverse(NODE* head) { if (head == NulL || head->next == NulL) { return head; } NODE* new_head = reverse(head->next); // 反转指针 head->next->next = head; head->next = NulL; return new_head; }
打印链表
/* 打印队列 */ voID print(NODE* head) { NODE* temp = head; while (temp != NulL) { std::cout << temp->data << std::endl; temp = temp->next; } }
完整代码如下:
#include <iostream> /* 节点结构 */ struct NODE { int data; struct NODE* next; }; /* 添加元素-压栈 */ voID push(NODE** head,int dat) { struct NODE* new_node = new NODE(); new_node->data = dat; new_node->next = *head; *head = new_node; } /* 添加元素-添加 */ voID add(NODE** head,int dat) { struct NODE* new_node = new NODE(); new_node->data = dat; new_node->next = NulL; if (*head != NulL) { struct NODE* temp = *head; while (temp->next != NulL) { temp = temp->next; } temp->next = new_node; } else { *head = new_node; } } /* 反转列表 */ voID reverse(NODE** head) { struct NODE* pre = NulL; struct NODE* cur = *head; struct NODE* nxt; while (cur != NulL) { // 反转指针 nxt = cur->next; cur->next = pre; // 移动指针 pre = cur; cur = nxt; } *head = pre; } /* 反转列表-复制原表返回反转表 */ NODE* reverse(NODE* head) { if (head == NulL || head->next == NulL) { return head; } NODE* new_head = reverse(head->next); // 反转指针 head->next->next = head; head->next = NulL; return new_head; } /* 打印队列 */ voID print(NODE* head) { NODE* temp = head; while (temp != NulL) { std::cout << temp->data << std::endl; temp = temp->next; } } int main() { struct NODE* n = NulL; add(&n,1); add(&n,2); add(&n,3); n = reverse(n); print(n); return 0; }
希望本文所述对大家C++程序设计有所帮助。
以上是大佬教程为你收集整理的C++数据结构与算法之反转链表的方法详解全部内容,希望文章能够帮你解决C++数据结构与算法之反转链表的方法详解所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。