有一个带头结点的双链表L,设计一个算法将其所有元素逆置,即第1个元素变为最后一个元素,第2个元素变为倒数第2个元素,…,最后一个元素变为第1个元素。代码
时间: 2024-09-20 20:03:42 浏览: 43
在双链表中逆置元素,你可以采用迭代或递归的方式。这里给出一个简单的迭代算法:
首先,我们需要定义两个指针,一个称为`prev`,初始指向`None`,用于保存当前节点的前一个节点;另一个称为`current`,初始设置为头节点`head`。
然后,进入一个循环,直到`current`变为`None`:
1. 检查当前节点是否为空,如果为空则直接返回,因为已经到了链表的末尾。
2. 将当前节点的下一个节点赋值给临时变量`temp`,这是为了在交换节点后保存原下一个节点。
3. 更新当前节点的下一个节点为其前一个节点,即`current.next = prev`。
4. 将`prev`移动到当前节点,即`prev = current`,准备处理下一对相邻节点。
5. 再次将`current`移动到`temp`,即`current = temp`,继续循环。
最后,当循环结束,将原始的头节点`head`设为新的`prev`,即`head = prev`,这样就完成了整个链表的逆置。
以下是Python代码示例:
```python
class Node:
def __init__(self, value=None, next=None, prev=None):
self.value = value
self.next = next
self.prev = prev
def reverse_linked_list(head):
prev = None
current = head
while current is not None:
temp = current.prev
current.prev = current.next
current.next = prev
prev = current
current = temp
return prev
```
阅读全文