热门标签 | HotTags
当前位置:  开发笔记 > IOS > 正文

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

这篇文章主要介绍了C++数据结构与算法之反转链表的方法,结合实例形式分析了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 <data <next;
 }
}

完整代码如下:

#include 
/* 节点结构 */
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 <data <next;
  }
}
int main() {
  struct NODE* n = NULL;
  add(&n, 1);
  add(&n, 2);
  add(&n, 3);
  n = reverse(n);
  print(n);
  return 0;
}

希望本文所述对大家C++程序设计有所帮助。


推荐阅读
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • C++实现经典排序算法
    本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出,帮助读者全面了解这些排序方法的特点。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 非公版RTX 3080显卡的革新与亮点
    本文深入探讨了图形显卡的进化历程,重点介绍了非公版RTX 3080显卡的技术特点和创新设计。 ... [详细]
  • 本文基于刘洪波老师的《英文词根词缀精讲》,深入探讨了多个重要词根词缀的起源及其相关词汇,帮助读者更好地理解和记忆英语单词。 ... [详细]
  • 本文介绍如何在 Xcode 中使用快捷键和菜单命令对多行代码进行缩进,包括右缩进和左缩进的具体操作方法。 ... [详细]
  • 如何在PHPcms网站中添加广告
    本文详细介绍了在PHPcms网站后台添加广告的方法,涵盖多种常见的广告形式,如百度广告和Google广告,并提供了相关设置的步骤。同时,文章还探讨了优化网站流量的SEO策略。 ... [详细]
  • 当iOS设备越狱后,某些插件可能会导致系统崩溃(白苹果)。此时,可以通过进入安全模式来排查并删除有问题的插件。本文将详细介绍如何通过特定按键组合进入不加载MobileSubstrate的安全模式,并提供相关背景知识。 ... [详细]
  • 在Linux系统中配置并启动ActiveMQ
    本文详细介绍了如何在Linux环境中安装和配置ActiveMQ,包括端口开放及防火墙设置。通过本文,您可以掌握完整的ActiveMQ部署流程,确保其在网络环境中正常运行。 ... [详细]
  • C++: 实现基于类的四面体体积计算
    本文介绍如何使用C++编程语言,通过定义类和方法来计算由四个三维坐标点构成的四面体体积。文中详细解释了四面体体积的数学公式,并提供了两种不同的实现方式。 ... [详细]
  • 本文介绍如何通过Windows批处理脚本定期检查并重启Java应用程序,确保其持续稳定运行。脚本每30分钟检查一次,并在需要时重启Java程序。同时,它会将任务结果发送到Redis。 ... [详细]
  • 如何优化2060显卡设置以提升《Apex英雄》游戏体验
    《Apex英雄》作为一款热门的战术竞技游戏,吸引了大量玩家。本文将探讨如何通过优化GeForce RTX 2060显卡设置,确保在《Apex英雄》中获得最佳性能和流畅的游戏体验。 ... [详细]
  • 本章将深入探讨移动 UI 设计的核心原则,帮助开发者构建简洁、高效且用户友好的界面。通过学习设计规则和用户体验优化技巧,您将能够创建出既美观又实用的移动应用。 ... [详细]
  • 本文介绍如何通过SQL查询从JDE(JD Edwards)系统中提取所有字典数据,涵盖关键表的关联和字段选择。具体包括F0004和F0005系列表的数据提取方法。 ... [详细]
  • 如何高效创建和使用字体图标
    在Web和移动开发中,为什么选择字体图标?主要原因是其卓越的性能,可以显著减少HTTP请求并优化页面加载速度。本文详细介绍了从设计到应用的字体图标制作流程,并提供了专业建议。 ... [详细]
author-avatar
周天芷65486
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有