c++反转链表|极客笔记

c++反转链表

在数据结构和算法中，链表是一种常见的数据结构，它由节点组成，每个节点包含数据和一个指向下一个节点的指针。反转链表是一个常见的问题，涉及将链表中的节点顺序颠倒。在本文中，我们将使用C++语言实现如何反转一个链表。我们将介绍反转链表的概念，讨论算法实现细节，并给出C++代码示例。

反转链表的概念

反转链表是指将链表中的节点顺序颠倒，使链表的尾部成为头部，头部成为尾部。例如，对于一个链表1->2->3->4->5，反转之后变为5->4->3->2->1。

算法实现

下面我们来讨论一种基于迭代的算法来反转链表。算法的基本思路如下：

初始化三个指针prev、curr、next，分别指向当前节点的前一个节点、当前节点和当前节点的下一个节点。
遍历链表，直到当前节点为空：

将当前节点的next指针指向prev，完成当前节点的反转。
更新prev、curr、next指针，将它们向右移动一个位置。
1. 最后返回prev指针作为新链表的头节点。

C++代码实现

下面是用C++实现反转链表的示例代码：

#include <iostream>

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

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    ListNode* next = nullptr;

    while (curr != nullptr) {
        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 != nullptr) {
        std::cout << newHead->val << " ";
        newHead = newHead->next;
    }

    return 0;
}

在上面的示例代码中，我们定义了一个结构体ListNode，表示链表的节点。reverseList函数接收一个头节点指针，然后对链表进行反转。在main函数中，我们创建了一个包含5个节点的链表，并调用reverseList函数进行反转。最后遍历新链表，输出节点的值。