[已解决]将链表反转的问题

白痴爱面包

1.设计一个函数，传入链表的头指针，实现将链表反转。
示例：
链表节点定义：
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
函数接口定义：
ListNode* reverseList(ListNode* head) {
//完成该函数
}

最佳答案

月排行榜 / 总排行榜

isdkz

2023-4-2 21:19:19

在这个问题中，我们需要实现一个函数 reverseList，它接收一个链表的头指针，然后将链表反转。我们可以通过迭代或递归的方式来实现这个功能。这里，我将展示一种迭代的实现方法：

#include <iostream>

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

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr; // 初始化前一个节点指针
    ListNode* current = head; // 初始化当前节点指针
    ListNode* nextNode = nullptr; // 初始化下一个节点指针

    while (current != nullptr) {
        nextNode = current->next; // 保存当前节点的下一个节点
        current->next = prev; // 将当前节点的下一个节点指向前一个节点，完成反转
        prev = current; // 更新前一个节点为当前节点
        current = nextNode; // 更新当前节点为下一个节点
    }

    return prev; // 返回反转后链表的头节点
}

int main() {
    // 构造一个简单的链表：1 -> 2 -> 3 -> nullptr
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);

    // 反转链表并打印
    ListNode* reversedHead = reverseList(head);
    while (reversedHead != nullptr) {
        std::cout << reversedHead->val << " -> ";
        reversedHead = reversedHead->next;
    }
    std::cout << "nullptr" << std::endl;

    return 0;
}

这个代码中，reverseList 函数首先初始化了 prev、current 和 nextNode 三个指针。然后通过一个 while 循环遍历链表中的每个节点，

将当前节点的 next 指针指向前一个节点以实现反转。在循环中，我们会更新 prev 和 current 指针以便处理下一个节点。

最后，当 current 指针指向 nullptr 时，循环结束，返回 prev 指针，即反转后链表的头节点。

跳转到最佳答案楼层

isdkz

在这个问题中，我们需要实现一个函数 reverseList，它接收一个链表的头指针，然后将链表反转。我们可以通过迭代或递归的方式来实现这个功能。这里，我将展示一种迭代的实现方法：

#include <iostream>

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

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr; // 初始化前一个节点指针
    ListNode* current = head; // 初始化当前节点指针
    ListNode* nextNode = nullptr; // 初始化下一个节点指针

    while (current != nullptr) {
        nextNode = current->next; // 保存当前节点的下一个节点
        current->next = prev; // 将当前节点的下一个节点指向前一个节点，完成反转
        prev = current; // 更新前一个节点为当前节点
        current = nextNode; // 更新当前节点为下一个节点
    }

    return prev; // 返回反转后链表的头节点
}

int main() {
    // 构造一个简单的链表：1 -> 2 -> 3 -> nullptr
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);

    // 反转链表并打印
    ListNode* reversedHead = reverseList(head);
    while (reversedHead != nullptr) {
        std::cout << reversedHead->val << " -> ";
        reversedHead = reversedHead->next;
    }
    std::cout << "nullptr" << std::endl;

    return 0;
}

这个代码中，reverseList 函数首先初始化了 prev、current 和 nextNode 三个指针。然后通过一个 while 循环遍历链表中的每个节点，

将当前节点的 next 指针指向前一个节点以实现反转。在循环中，我们会更新 prev 和 current 指针以便处理下一个节点。

最后，当 current 指针指向 nullptr 时，循环结束，返回 prev 指针，即反转后链表的头节点。