设计一个算法,将链表123456789中所有节点的链接方向“原地”逆转,即要求仅利用原表的储存空间
时间: 2024-09-20 13:13:06 浏览: 41
逆转交替合并两个链表的解析与实现
这个问题是关于链表数据结构的反转操作。你可以使用迭代或递归的方式来原地逆转一个单向链表。这里提供一个迭代的方法:
**迭代法**:
1. 创建两个指针,`prev` 和 `current`,初始时都指向 `NULL` 和链表的头结点。
2. 进入循环,当 `current` 不为空时,做以下步骤:
- 保存当前节点的下一个节点,`nextNode = current->next`。
- 更新当前节点的 `next` 指向 `prev`,即 `current->next = prev`。
- 移动指针,`prev = current`, `current = nextNode`。
3. 当循环结束,链表头部的 `prev` 就会变成新的头结点。
这个算法不会创建额外的存储空间,因为所有的修改都在原有的链表节点上完成。
```plaintext
伪代码:
function reverseList(head):
prev = None
current = head
while current is not None:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
```
阅读全文