用c++实现单链表的逆置

要实现C++单链表的逆置，可以按照以下步骤操作[^1]：

// 假设有一个结构体定义了链表节点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 函数来逆置链表
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr; // 初始化前驱节点为空
    ListNode* curr = head;   // 初始化当前节点为头节点

    // 当链表非空时，继续遍历并交换节点指针
    while (curr != nullptr) {
        ListNode* temp = curr->next; // 保存下一个节点
        curr->next = prev;         // 更新当前节点的next指向prev
        prev = curr;               // 更新prev指向当前节点
        curr = temp;               // 移动到下一个节点
    }

    return prev; // 返回新的头节点，即原链表的尾节点
}

这段代码创建了一个名为`reverseList`的函数，它接受链表的头节点作为参数，通过迭代的方式逆置链表，并返回新的头节点。注意这个过程不需要额外存储完整的链表副本[^2]。

相关问题

c++ 单链表逆置函数

在C++中，单链表逆置的函数可以使用引用中的代码实现。代码中首先判断链表是否为空，如果为空则返回NULL。然后创建一个新的头结点newHead，并将其赋值为原链表的最后一个结点的数据。接下来创建一个指针newTail，用于指向新链表的尾部定位。然后从原链表的倒数第二个结点开始遍历，依次创建新的结点newNode，并将其数据赋值为对应位置的原链表结点的数据。然后将newTail的link指向newNode，并将newNode的link指向NULL。最后更新newTail的位置为newNode，完成一次逆置。最终返回newHead即可得到逆置后的单链表。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [线性表逆置--顺序表\单链表逆置](https://blog.csdn.net/weixin_60344133/article/details/127582855)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]

头插法实现单链表逆置 数据结构C++版

头插法（即反转链表）是指通过在新链表的头部插入元素，逐步构建新的逆序链表。以下是使用C++实现单链表逆置的一种方法：

#include <iostream>

// 定义链表节点结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 使用头插法逆置链表
ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {  // 特殊情况：空链表或只有一个节点
        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;  // 返回逆序后的头节点
}

// 打印链表
void printList(ListNode* head) {
    ListNode* temp = head;
    while (temp != nullptr) {
        std::cout << temp->val << " -> ";
        temp = temp->next;
    }
    std::cout << "nullptr\n";
}

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

在这个例子中，我们先检查链表是否为空或只有一个节点，如果是则直接返回。接着，我们通过三个指针prev、curr和nextTemp，分别表示前驱、当前和原始的下一个节点。在每次循环中，我们将curr的next指向前驱节点，然后移动prev和curr。当遍历完整个链表后，prev就是新的头节点。