用头插法实现链表逆置c++

头插法是一种常见的链表逆置算法，它通过不断将当前节点插入到已反转链表的头部来达到逆序的效果。以下是使用C++实现头插法链表逆置的基本步骤：

#include <iostream>

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

// 使用头插法逆置链表
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr; // 初始化前驱指针为空
    ListNode* current = head; // 初始化当前指针指向头结点

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

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

int main() {
    // 创建一个示例链表
    ListNode* list = new ListNode(1);
    list->next = new ListNode(2);
    list->next->next = new ListNode(3);
    list->next->next->next = new ListNode(4);

    std::cout << "Original List:" << std::endl;
    printList(list);

    // 逆置链表
    list = reverseList(list);

    std::cout << "Reversed List:" << std::endl;
    printList(list);

    return 0;
}

在这个例子中，`reverseList`函数接收一个链表头节点作为输入，通过遍历链表并将每个节点的next指针指向前一个节点，实现了链表的逆序。