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

—-想了解C++数据结构与算法之反转链表的方法详解分享的全部内容且更多的C语言教程关注<计算机技术网(www.ctvol.com)!!>

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++程序设计有所帮助。