C++反转单链表

反转单链表可以通过修改节点之间的指针来实现。具体步骤可以参考下面的代码示例：

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

ListNode* reverseList(ListNode* head) {
    ListNode *prev = NULL;
    ListNode *cur = head;
    while (cur != NULL) {
        ListNode *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

上述代码中，我们使用了三个指针来遍历单链表。`prev`指向上一个节点，`cur`指向当前节点，`next`指向下一个节点。在遍历过程中，我们将`cur`指向的节点的`next`指针指向`prev`，然后将`prev`指向`cur`，`cur`指向`next`，继续遍历。最后返回`prev`，即为反转后的链表头节点。

相关问题

C++实现单链表的就地逆置

在C++中，单链表的就地逆置（也称原地逆序或反转）是指不额外分配空间，直接修改原有链表节点的指针，使得整个链表的顺序反转。以下是通过迭代方法实现的一种简单方法：

#include <iostream>

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

void reverseList(ListNode* &head) {
    if (head == nullptr || head->next == nullptr) {
        return; // 如果链表为空或者只有一个节点，无需反转
    }

    ListNode *prev = nullptr, *curr = head, *nextTemp = nullptr;

    // 遍历链表，每次把当前节点的下一个节点保存到临时变量，然后更新当前节点的next指向其前一个节点
    while (curr != nullptr) {
        nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }

    // 最后，原来的头节点变成新的尾节点
    head = prev;
}

// 测试
int main() {
    ListNode *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    
    std::cout << "Original list: ";
    printList(head); // 输出原始链表

    reverseList(head);

    std::cout << "Reversed list: ";
    printList(head); // 输出反转后的链表

    return 0;
}

// 辅助函数：打印链表
void printList(ListNode* node) {
    while (node != nullptr) {
        std::cout << node->val << " -> ";
        node = node->next;
    }
    std::cout << "nullptr" << std::endl;
}

用c++编写单链表的删除并使其逆置输出

好的，下面是用C++实现单链表删除并逆置输出的示例代码：

#include <iostream>
using namespace std;

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

// 删除链表中指定值的节点
ListNode* removeElements(ListNode* head, int val) {
    ListNode* dummy = new ListNode(0);  // 哑节点
    dummy->next = head;
    ListNode* prev = dummy;
    ListNode* curr = head;
    while (curr != nullptr) {
        if (curr->val == val) {
            prev->next = curr->next;
            delete curr;
            curr = prev->next;
        } else {
            prev = curr;
            curr = curr->next;
        }
    }
    head = dummy->next;
    delete dummy;
    return head;
}

// 反转链表
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// 输出链表
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "null" << endl;
}

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);
    // 删除链表中指定值的节点
    head = removeElements(head, 3);
    // 反转链表并输出
    head = reverseList(head);
    printList(head);
    // 释放链表内存
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* temp = curr;
        curr = curr->next;
        delete temp;
    }
    return 0;
}

该代码先创建了一个单链表，然后调用 `removeElements()` 函数删除值为 3 的节点。接着调用 `reverseList()` 函数反转链表，并最终调用 `printList()` 函数输出链表。最后释放链表内存。