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(nullptr) {}
};

// 迭代方法反转单链表
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* nextTemp = curr->next; // 保存下一个节点
        curr->next = prev; // 反转当前节点的指针
        prev = curr; // 移动prev指针
        curr = nextTemp; // 移动curr指针
    }
    return prev; // 返回新的头节点
}

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

int main() {
    // 创建链表 1->2->3->4->5
    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;
}

这个示例代码定义了一个链表节点结构 `ListNode`，并实现了 `reverseList` 函数来反转单链表。`printList` 函数用于打印链表内容。在 `main` 函数中，我们创建了一个示例链表并进行了反转操作。

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