用C++设计一个算法,将链表中所有结点的链接方向“原地”逆转,即要求仅利用原表的存储空间,换句话说,要求算法的空间复杂度为O(1)。
时间: 2024-10-12 14:14:00 浏览: 40
单链表的创建于逆转
在C++中,可以使用迭代的方式来原地反转单向链表。这是一种常见的链表操作,可以通过三个指针,两个前驱节点和一个当前节点,依次改变它们之间的链接来完成。以下是详细的步骤:
```cpp
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head; // 如果链表为空或只有一个节点,直接返回
}
ListNode *prev = nullptr, *curr = head, *nextTemp = nullptr; // 定义三个指针
while (curr != nullptr) { // 当还有节点存在
nextTemp = curr->next; // 将下一个节点暂存
curr->next = prev; // 更新当前节点指向前一个节点
prev = curr; // 移动前驱节点
curr = nextTemp; // 移动当前节点到下一个节点
}
return prev; // 返回新的头节点,即原链表的尾部
}
```
在这个算法中,我们遍历链表一次,每一步都只修改了三个节点的连接,所以空间复杂度确实是O(1),因为我们没有额外的存储空间。
阅读全文