单链表逆置C++头插法

单链表的逆置头插法是指通过遍历原链表，将每个节点插入到新链表的头部，从而达到链表反转的效果。这里是一个简单的C++实现步骤：

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr; // 新链表的头指针，初始化为NULL
    ListNode* curr = head; // 当前节点，初始化为原链表头

    while (curr != nullptr) { // 遍历整个原链表
        ListNode* next_temp = curr->next; // 保存当前节点的下一个节点
        curr->next = prev; // 将当前节点的next指向前一个节点
        prev = curr; // 更新prev指向当前节点，准备处理下一个节点
        curr = next_temp; // 将curr移动到下一个节点
    }

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

在这个过程中，每次循环我们都改变了当前节点的`next`指向前一个节点，然后更新两个指针以便下一次迭代。当遍历结束时，`prev`就是新的头节点。

相关问题

头插法实现单链表逆置 数据结构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就是新的头节点。

利用尾插法建立单链表，利用头插法完成单链表的逆置并输出逆置后的单链表

好的，我可以帮你解答这个问题。

首先，让我们了解一下尾插法建立单链表的思路：

1. 定义一个头指针和一个尾指针，初始时它们都指向头结点；
2. 定义一个新结点，输入数据；
3. 将新结点插入到尾结点之后，并将尾指针指向新结点；
4. 重复步骤2和3，直到输入完所有数据。

接下来，我们来看一下头插法完成单链表的逆置并输出逆置后的单链表的思路：

1. 定义一个新链表的头结点，并初始化为空；
2. 从原链表的头结点开始，依次取出每个节点，将其插入到新链表的头结点之后；
3. 重复步骤2，直到原链表中的所有节点都被取出并插入到新链表中；
4. 输出新链表的所有节点。

下面是C++代码实现尾插法建立单链表和头插法完成单链表的逆置并输出逆置后的单链表：

#include <iostream>
using namespace std;

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

ListNode* createList() {
    ListNode* head = new ListNode(0);
    ListNode* tail = head;
    int x;
    while (cin >> x) {
        ListNode* p = new ListNode(x);
        tail->next = p;
        tail = p;
    }
    return head->next;
}

ListNode* reverseList(ListNode* head) {
    ListNode* newHead = nullptr;
    while (head) {
        ListNode* p = head;
        head = head->next;
        p->next = newHead;
        newHead = p;
    }
    return newHead;
}

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

int main() {
    ListNode* head = createList();
    head = reverseList(head);
    printList(head);
    return 0;
}

希望能够帮到你！