用C++设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间

在C++中，你可以使用迭代的方式，通过三个指针`prev`, `current`, 和`next`来实现单向链表的反转。这里是一个简单的算法：

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; // 将当前节点指向前驱
        prev = current; // 更新前驱为当前节点
        current = nextTemp; // 更新当前节点为下一个节点
    }

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

这个算法的工作原理是每次迭代都改变当前节点的`next`指向前一个节点，直到遍历到链表的末尾。最后返回`prev`作为新链表的头节点。

相关问题

设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。用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* nextTemp = curr->next;

        // 将当前节点的next指向前驱节点
        curr->next = prev;

        // 指针前移
        prev = curr;
        curr = nextTemp;
    }

    // 返回新的头节点（实际上是原链表的尾节点）
    return prev;
}

在这个算法中，我们从头节点开始，每次迭代都将当前节点的`next`指向前一个节点，然后前进到下一个未处理的节点。当所有节点都处理完毕后，原来的尾节点变成了新的头节点，实现了链表的反转。

5．请用C/C+＋语言设计算法，通过遍历一趟，将链表中所有结点的链接方向逆转 ，仍利用原表的存储空间。

为了反转一个单向链表，你可以创建一个新的指针，并通过迭代的方式，每次交换当前节点与其前驱节点的指针。以下是使用C++实现该算法的一个简单示例：

#include <iostream>

struct Node {
    int data;
    Node* next;
};

// 创建新节点
Node* createNode(int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = nullptr;
    return newNode;
}

// 反转链表函数
void reverseList(Node** head) {
    Node* prev = nullptr;
    Node* current = *head;
    Node* nextTemp = nullptr;

    // 遍历链表
    while (current != nullptr) {
        // 保存当前节点的下一个节点
        nextTemp = current->next;

        // 将当前节点的next指向前一个节点
        current->next = prev;

        // 更新prev、current
        prev = current;
        current = nextTemp;
    }

    // 设置新的头节点为原头节点的前一个节点
    *head = prev;
}

// 打印链表
void printList(Node* node) {
    while (node != nullptr) {
        std::cout << node->data << " ";
        node = node->next;
    }
    std::cout << "\n";
}

int main() {
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);

    std::cout << "Original list: ";
    printList(head);

    reverseList(&head);

    std::cout << "Reversed list: ";
    printList(head);

    return 0;
}

这个程序首先定义了一个链表节点结构，接着创建了`reverseList`函数，它接受链表头节点的地址作为参数。在函数内部，通过三个指针`prev`、`current`和`nextTemp`，分别代表前一个节点、当前节点和临时储存当前节点的下一个节点。遍历过程中，每一步都改变了节点的指向，使得最后链表的方向发生反转。