数据结构中,设计一个算法,通过一趟遍历,将链表中所有结点的链接方向逆转,且仍利用原表的存储空间。
时间: 2024-09-17 20:04:33 浏览: 67
考研数据结构算法经典.doc
在数据结构中,设计一个反转单链表的算法通常会采用迭代或者递归的方式。这里提供一种常见的迭代方法:
1. **迭代法**:
- 初始化两个指针,一个当前节点(current)和前一个节点(prev),初始都设为 `null`。
- 遍历链表,对于每个节点:
- 将当前节点的 `next` 指向前一个节点,即 `current.next = prev`。
- 更新前一个节点和当前节点,`prev = current`, `current = current.next`。
- 当遍历到链表尾部时,链表头节点的 `next` 应该是指向 `null`,所以最后将原头节点指向 `prev`,完成反转。
```python
def reverseList(head):
prev = None
current = head
while current is not None:
next_temp = current.next
current.next = prev
prev = current
current = next_temp
return prev
```
阅读全文