C++数据结构与算法之反转链表的方法详解

时间:2021-05-20

本文实例讲述了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++程序设计有所帮助。

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章