设有一个表头指针为list的不带附加头结点的非空单链表。设计一个C++算法,通过遍历一趟链表,将链表中所有结点的链接方向逆转。不允许引入额外的空间复杂度
时间: 2024-10-06 10:05:51 浏览: 18
在C++中,可以使用迭代的方式来反转一个不带附加头节点的非空单链表。下面是具体的算法实现:
```cpp
#include <iostream>
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;
ListNode* curr = head;
while (curr != nullptr) {
// 保存当前节点的下一个节点
ListNode* nextTemp = curr->next;
// 反转当前节点的指向
curr->next = prev;
// 更新prev和curr指针
prev = curr;
curr = nextTemp;
}
return prev; // 返回新的头节点
}
// 打印链表帮助测试
void printList(ListNode* head) {
ListNode* temp = head;
while (temp != nullptr) {
std::cout << temp->val << " ";
temp = temp->next;
}
std::cout << "\n";
}
int main() {
// 创建一个链表示例
ListNode* list = new ListNode(1);
list->next = new ListNode(2);
list->next->next = new ListNode(3);
list->next->next->next = new ListNode(4);
std::cout << "Original List: ";
printList(list);
list = reverseList(list); // 反转链表
std::cout << "Reversed List: ";
printList(list);
return 0;
}
```
在这个代码中,我们维护了三个指针:`prev` 用于记录前一个节点,`curr` 用于访问当前节点,`nextTemp` 用于临时存储`curr`节点的下一个节点。每一步都把`curr`的`next`指向前一个节点`prev`,然后更新`prev`和`curr`指向下一个节点。最后返回反转后的`prev`节点,它成为了新的头节点。
运行这段代码可以看到链表的方向是如何被逆转的。这个算法的时间复杂度是O(n),其中n是链表的长度,因为每个节点都被遍历一次。空间复杂度是O(1),因为我们只使用了常数级别的额外空间。