用C语言设计一个算法,将链表中所有节点的链接方向“原地”逆转,即要求仅利用原表的存储空间,换句话说,要求算法的空间复杂度为0(1)。
时间: 2024-09-30 20:02:45 浏览: 19
在C语言中,要原地逆转单向链表,可以使用迭代的方式。以下是简单的步骤:
1. 定义两个指针`prev`和`current`,初始时都指向头结点`head`(假设已存在)。
2. 开始一个循环,直到`current`为NULL(表示链表结束):
a. 将`current`的下一个节点`next`保存到临时变量`temp`中。
b. 将`current`的`next`指针更新为`prev`。
c. `prev`和`current`分别向前移动一位,即`prev = current`, `current = temp`.
3. 循环结束后,`prev`会指向新的头结点,因为所有的节点已经被反转了链接。
下面是伪代码形式:
```c
Node* reverseList(Node* head) {
Node* prev = NULL;
Node* current = head;
while (current != NULL) {
Node* nextTemp = current->next; // 保存当前节点的下一个节点
current->next = prev; // 反转当前节点的指针
prev = current; // 移动prev指针
current = nextTemp; // 移动current指针
}
return prev; // 返回新头结点
}
```