利用单链表作为存储结构。先建立线性表的带头结点单链表表示形式,之后在不借助辅助结点空间的情况下实现单链表的逆置,并将结果输出
时间: 2024-09-21 21:09:25 浏览: 40
单链表逆置-第2章 线性表
为了在不借助辅助结点空间的情况下实现单链表的逆置,我们可以直接遍历原链表并在当前节点上修改其`next`指针。这是一种称为"就地逆置"的方法。下面是具体的步骤[^1]:
1. 初始化两个指针,`prev`初始化为`None`(表示无前驱),`curr`设置为链表的头结点`head`。
2. 当`curr`不为`None`时,执行以下操作:
- 记录当前节点的下一个节点:`temp = curr.next`。
- 更新当前节点的`next`指针,使其指向前一个节点:`curr.next = prev`。
- 移动指针:`prev = curr`,`curr = temp`。
3. 最后,更新链表的头结点:`head = prev`,因为现在`prev`指向的是新的头结点。
这样,我们就完成了单链表的逆置,无需额外的空间。下面是一个简单的Python实现:
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
def reverse_list(head):
prev = None
curr = head
while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prev
# 示例
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
reversed_head = reverse_list(head)
# 原始链表: 1 -> 2 -> 3
# 逆置后: 3 -> 2 -> 1
# 输出逆置后的链表,这里仅打印节点数据,实际应用中可能需要递归遍历打印
while reversed_head:
print(reversed_head.data, end=" -> ")
reversed_head = reversed_head.next
```
阅读全文