C++链表反转代码示例 |21xrx.com

C++链表反转代码示例

2023-07-01 02:55:46 深夜i -- --

C++ 链表反转代码示例

在C++编程中，链表是一种常见的数据结构。当我们需要对链表进行反转操作时，可以使用以下代码示例：


#include <iostream>
using namespace std;
// 链表节点结构
struct Node {
  int data;
  Node* next;
  Node(int d) : data(d), next(nullptr) {}
};
// 反转链表函数
Node* reverseList(Node* head) {
  // 当链表为空或只有一个节点时
  if (head == nullptr || head->next == nullptr)
    return head;
  
  
  // 反转后的链表头节点
  Node* newHead = nullptr;
  
  while (head) {
    // 保存原链表下一个节点
    Node* next = head->next;
    // 将当前节点连接到新链表头部
    head->next = newHead;
    // 更新新链表头部为当前节点
    newHead = head;
    // 更新当前节点为原链表下一个节点
    head = next;
  }
  
  return newHead;
}
// 打印链表函数
void printList(Node* head) {
  while (head)
    cout << head->data << " ";
    head = head->next;
  
  cout << endl;
}
int main() {
  // 创建一个链表：1 -> 2 -> 3 -> 4 -> 5
  Node* head = new Node(1);
  Node* node2 = new Node(2);
  Node* node3 = new Node(3);
  Node* node4 = new Node(4);
  Node* node5 = new Node(5);
  head->next = node2;
  node2->next = node3;
  node3->next = node4;
  node4->next = node5;
  
  // 打印原链表
  cout << "原链表：";
  printList(head);
  
  // 反转链表
  head = reverseList(head);
  
  // 打印反转后的链表
  cout << "反转后的链表：";
  printList(head);
  
  // 释放链表内存
  Node* tmp = head;
  while (head)
    tmp = head;
    head = head->next;
    delete tmp;
  
  return 0;
}

上述代码首先定义了一个链表节点结构体，其中包含数据和指向下一个节点的指针。接着，定义了链表反转函数reverseList，该函数接收链表头节点作为参数，返回反转后的链表头节点。

具体的反转操作采用了迭代的方式实现，利用一个新链表的头节点newHead和原链表的头节点head，依次遍历原链表各节点，并将其依次连接到新链表的头部。最后返回新链表的头节点即为反转后的链表头节点。

最后，我们在主函数中创建了一个链表1 -> 2 -> 3 -> 4 -> 5，并分别打印原链表和反转后的链表。同时，在程序结束前需要释放链表内存，避免内存泄漏。

上一篇: idea打包java可执行jar包

下一篇: C++ 多线程面试题

评论区

()

相似文章