C语言编写,使用常数附加空间,以O(N)时间反转单链表
时间: 2024-09-27 20:13:53 浏览: 38
2的n次方 单链表操作 c语言
4星 · 用户满意度95%
在C语言中,反转单链表通常是通过迭代或递归的方式实现的,而不是直接附加额外的空间。如果需要考虑添加常数附加空间,一种常见的做法是在原地修改链表节点,不需要额外存储整个链表的信息。这里我们假设可以访问下一个节点的指针以及当前节点。
下面是一个简单的迭代方法,时间复杂度确实是O(N),其中N是链表的长度:
```c
struct ListNode {
int val;
struct ListNode *next;
};
void reverseList(struct ListNode **head) {
if (*head == NULL || (*head)->next == NULL) {
return; // 如果链表为空或只有一个节点,无需反转
}
struct ListNode *prev = NULL, *curr = *head, *nextTemp;
while (curr != NULL) {
nextTemp = curr->next; // 保存当前节点的下一个节点
curr->next = prev; // 将当前节点指向prev
prev = curr; // 移动prev到curr
curr = nextTemp; // 移动curr到下一个未处理的节点
}
*head = prev; // 更新头节点为新的头
}
```
在这个代码中,仅使用了三个临时变量`prev`, `curr`, 和`nextTemp`,它们都是常量级别的空间。每次循环更新指针即可完成链表的反转。
阅读全文