将原链表逆转成一个新的链表

在C++中，反转一个链表通常涉及到三个关键步骤：遍历当前节点，找到它的后继节点（指向下一个元素），然后交换它们的指针。这里是一个简单的单链表反转的例子：

#include <iostream>

// 定义链表节点结构
struct ListNode {
    int val; // 节点值
    ListNode* next; // 指向下一个节点的指针
    ListNode(int x) : val(x), next(nullptr) {} // 构造函数
};

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr; // 初始化前驱为NULL
    ListNode* curr = head; // 初始化当前为头结点

    while (curr != nullptr) { // 当当前不为空时
        ListNode* temp = curr->next; // 保存当前节点的下一个节点
        curr->next = prev; // 将当前节点的next指向前驱
        prev = curr; // 前驱移动到当前节点
        curr = temp; // 当前节点移动到下一个节点
    }
    
    return prev; // 返回新链表的头结点，即原链表的尾部
}

int main() {
    // 创建示例链表
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    // ...

    // 反转链表
    ListNode* reversedHead = reverseList(head);

    // 打印反转后的链表
    while (reversedHead != nullptr) {
        std::cout << reversedHead->val << " -> ";
        reversedHead = reversedHead->next;
    }
    std::cout << "nullptr" << std::endl;

    // 清理内存
    delete reversedHead;

    return 0;
}

这段代码定义了一个`reverseList`函数，它接受一个链表的头结点`head`作为参数，通过迭代的方式逐步修改每个节点的`next`指针，实现了链表的反转。