c++ 链表反转

c++ 链表反转

在计算机科学中，链表是一种常见的数据结构，它由一系列节点组成，每个节点包含两部分：数据和指向下一个节点的指针。链表的节点可以动态地分配内存空间，相比数组，链表可以更方便地进行插入和删除操作。

链表的反转是指将链表中的节点按照相反的顺序重新排列。这在实际应用中有很多用途，比如在排序算法中、解决某些问题时可以使用链表反转。

链表反转的基本思路

要实现链表的反转，我们需要修改每个节点的指针，将其指向前一个节点。具体的流程如下：

1. 初始化三个指针：prev(前一个节点)、current(当前节点)、next(下一个节点)为nullptr。
2. 遍历链表，每次迭代都执行以下操作：

• 将 next 指向 current 的下一个节点。
• 将 current 指向 prev。
• 更新 prev 为 current。
• 更新 current 为 next。
  3. 返回反转后的头节点。

实现链表反转的 c++ 代码

下面是一个使用c++编写的链表反转程序，其中定义了链表节点的数据结构ListNode，以及实现了链表反转函数reverseList：

#include <iostream>

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

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

    while (current != nullptr) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    return prev;
}

void printList(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        std::cout << current->val << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

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);

    std::cout << "Original List: ";
    printList(head);

    head = reverseList(head);

    std::cout << "Reversed List: ";
    printList(head);

    return 0;
}

在上述代码中，我们定义了链表节点的结构ListNode，包含一个整数值val和指向下一个节点的指针next。reverseList函数用于反转链表，printList函数用于打印链表的值。在main函数中，我们构建了一个包含5个节点的链表，并打印了反转前和反转后的链表。

运行结果

编译并执行上述代码，得到的运行结果如下所示：

Original List: 1 2 3 4 5 
Reversed List: 5 4 3 2 1 

经过链表反转后，原链表中的节点顺序被逆序排列，符合我们的预期结果。

总结

链表反转是一个常见的算法问题，掌握其基本思路和实现方式对于提升编程能力和解决实际问题都是很有帮助的。通过本文的讲解和示例代码，相信读者已经对链表反转有了更深入的理解，希术能够在实际编程中灵活运用。