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

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

时间: 2025-02-16 08:16:13 浏览: 36

在C++中，要反转一个单向链表而保持原地操作（即只使用原链表的存储空间），我们可以使用迭代的方式，通过三个指针——`prev`, `current`, 和 `next` 来完成这项任务。以下是详细的步骤： 1. 初始化三个指针： - `prev` 初始设为 `nullptr`，表示前驱节点（反转后的后继节点） - `current` 设为链表头节点 2. 遍历链表，直到 `current` 为 `nullptr`： - 获取 `current` 的下一个节点，将其赋值给 `next` - 将 `current` 的 `next` 指针改为 `prev`，完成了当前节点的反转 - 更新 `prev` 和 `current` 分别为 `current` 和 `next` 3. 循环结束，`current` 已经变为原来的尾部，此时 `prev` 指向了新的头部，所以返回 `prev` 即可。下面是对应的C++代码实现： ```cpp 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; // 返回新链表的头节点 } ```

阅读全文