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

C++实现链表逆序

2023-07-11 04:55:40 深夜i 43 0

C++ 链表逆序指针循环

链表是一种非常常用的数据结构，它由一系列节点构成，每个节点包含数据和指向下一个节点的指针。链表有许多种类型，包括单向链表、双向链表和循环链表等。链表与数组相比，具有很多优点，比如可以动态添加或删除节点，不需要预先指定链表的长度等。

在C++中，我们可以使用指针来实现链表。链表的逆序是指将链表中的节点顺序颠倒，即原链表的最后一个节点变成新链表的第一个节点，原链表的第一个节点变成新链表的最后一个节点。实现链表逆序的方法有很多种，下面我将介绍其中一种。

方法一：迭代法

我们可以使用迭代法来实现链表逆序。具体方法如下：

1. 初始化三个指针，分别指向当前节点、前一个节点和下一个节点。

2. 遍历链表，对于每个节点，将其指向前一个节点，然后向前移动指针。

3. 当当前节点为NULL时，说明已经遍历完整个链表，新链表的头节点就是前一个节点。

下面是C++代码：

#include <iostream>
using namespace std;
struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseList(ListNode* head) { 
  ListNode *prev = NULL, *curr = head, *next = NULL;   
  while (curr != NULL)
    next = curr->next;
    curr->next = prev;
    prev = curr;
    curr = next;
     
  return prev;
}
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 *newHead = reverseList(head);
  while (newHead != NULL)
    cout << newHead->val << " ";
    newHead = newHead->next;
  
  return 0;
}

这段代码定义了一个链表节点结构体`ListNode`，其中`val`表示节点的值，`next`表示指向下一个节点的指针。`reverseList`函数实现了链表逆序，它的参数是链表的头节点，返回值也是链表的头节点。在`reverseList`函数中，我们定义了三个指针prev、curr和next来分别指向当前节点、前一个节点和下一个节点。开始时，prev和next都初始化为NULL，curr指向头节点。接下来，我们遍历链表，对于每个节点，将其指向前一个节点，然后向前移动指针。当遍历完整个链表时，新链表的头节点就是prev。

最后，在`main`函数中，我们创建一个链表，并调用`reverseList`函数将其逆序。然后，我们遍历新链表，输出每个节点的值。

总结

通过上述方法，我们可以用C++实现链表逆序。这种方法时间复杂度为O(n)，空间复杂度为O(1)。在实际应用中，链表逆序是一种常见的操作，因为它对于链表数据的处理起到了很好的作用。

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

下一篇: Visual C++ 2010 中文版

评论区

相似文章