C++实现链表逆序 |21xrx.com

C++实现链表逆序

2023-06-28 22:50:11 深夜i -- --

C++ 链表逆序

链表是一种常见的数据结构，而逆序是常见的链表操作之一。在C++中使用链表逆序是一项非常基本的技能，本文将介绍如何使用C++实现链表逆序操作。

首先，让我们来了解一下什么是链表。链表通过节点的方式储存一串数据，每个节点中都包含了指向下一个节点的指针，称为“下一个指针”。与其他数据结构相比，链表具有不需要连续内存空间的特点，因此可以动态地增加和删除节点，非常灵活。

接下来，我们需要写一个结构体来表示链表节点，该结构体至少包含一个指向下一个节点的指针和一个数据元素。


struct ListNode {
  int val;
  ListNode* next;
  ListNode(int x) : val(x), next(NULL) {}
};

这个结构体包含了一个整数类型的数据元素val和一个指向下一个节点的指针next，其中使用了C++ 11的特殊写法初始化了一个构造函数，其目的是为了给val成员赋值，并将next成员设为NULL。

接下来，我们需要写一个函数来实现链表逆序。该函数需要遍历整个链表，在遍历节点的同时，将每个节点的下一个指针指向上一个节点，从而实现逆序。


ListNode* reverseList(ListNode* head) {
  ListNode* pre = NULL;
  ListNode* cur = head;
  while (cur != NULL) {
    ListNode* tmp = cur->next;
    cur->next = pre;
    pre = cur;
    cur = tmp;
  }
  return pre;
}

这个函数实现了链表的逆序。我们首先定义了两个指针pre和cur，分别表示前一个节点和当前节点。在循环中，我们先将当前节点的下一个指针保存在临时变量tmp中，然后将当前节点的下一个指针指向前一个节点，接着将当前节点赋值给pre，将tmp赋值给cur，以此循环遍历整个链表。

最后，在主函数中调用reverseList函数，将链表第一个节点作为参数传入并输出结果。


int main() {
  ListNode* head = new ListNode(1);
  head->next = new ListNode(2);
  head->next->next = new ListNode(3);
  head->next->next->next = new ListNode(4);
  head->next->next->next->next = new ListNode(5);
  ListNode* res = reverseList(head);
  while (res != NULL)
    cout << res->val << " ";
    res = res->next;
  
  return 0;
}

以上就是使用C++实现链表逆序的步骤和代码。逆序操作是链表操作中最基本的操作之一，在日常开发中常常会用到。因此掌握这项技能对于C++程序员来说非常重要。

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

下一篇: C++文件打开失败的原因是什么？

评论区

()

相似文章