用C++完成逆置一个单链表为一个新表

在C++中，你可以通过迭代或递归的方式来逆置一个单链表。这里我将提供一种常见的迭代方法：

// 首先我们需要定义链表节点结构
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 迭代法逆置链表
ListNode* reverseList(ListNode* head) {
    if (head == NULL || head->next == NULL) {  // 特殊情况，链表为空或只有一个元素
        return head;
    }
    
    ListNode* prev = nullptr;  // 初始化前驱指针为NULL
    ListNode* curr = head;   // 当前指针指向头结点

    while (curr != nullptr) {  // 当前节点不为空
        ListNode* nextTemp = curr->next;  // 保存当前节点的下一个节点
        curr->next = prev;  // 将当前节点的next指向前驱节点
        prev = curr;  // 更新前驱节点为当前节点
        curr = nextTemp;  // 更新当前节点为原来保存的下一个节点
    }

    return prev;  // 返回新的头结点
}

在这个函数中，我们遍历链表一次，每次改变当前节点的`next`指向前一个节点，直到遍历完所有节点。最后返回的新头结点就是原链表的尾部。