用c++语言不用类的语句,用结构体 设计一个算法,将链表中所有节点的链接方向“原地”逆转,即要求仅利用原表的存储空间,换句话说,要求算法的空间复杂度为1
时间: 2024-12-08 13:16:44 浏览: 16
在C++中,你可以使用迭代的方式来实现链表的原地逆转。我们仍然使用`ListNode`结构体表示链表节点。原地逆转是指不需要额外的空间,只需要修改原有的链表节点指针即可。以下是详细的步骤:
```cpp
#include <iostream>
// 链表节点结构体
struct ListNode {
int val; // 节点值
ListNode* next; // 指向下一个节点的指针
};
// 原地逆转链表
void reverseList(ListNode*& head) {
if (head == nullptr || head->next == nullptr) { // 空链表或只有一个节点的情况
return;
}
ListNode* prev = nullptr; // 前驱节点,初始时为NULL
ListNode* curr = head; // 当前节点,初始时指向头节点
// 使用三个指针,不断更新它们的位置
while (curr != nullptr) {
ListNode* nextTemp = curr->next; // 保存当前节点的下一个节点
curr->next = prev; // 将当前节点的next指向前一个节点
prev = curr; // 前驱节点移到当前节点
curr = nextTemp; // 当前节点移到下一个节点
}
head = prev; // 最后,头节点变为原链表的最后一个节点
}
int main() {
ListNode* list = new ListNode{1, new ListNode{2, new ListNode{3, new ListNode{4, new ListNode{5}}}}};
std::cout << "Original linked list: ";
printList(head); // 印出原始链表
reverseList(head);
std::cout << "\nReversed linked list: ";
printList(head); // 印出逆转后的链表
delete list;
return 0;
}
// 辅助函数:打印链表
void printList(ListNode* node) {
while (node != nullptr) {
std::cout << node->val << " -> ";
node = node->next;
}
std::cout << "nullptr\n";
}
```
阅读全文