单链表中有n个结点,每个结点中包含一个整型键值,编写算法将其逆置。
时间: 2024-10-19 07:16:27 浏览: 18
单链表存储叶子节点并逆置
4星 · 用户满意度95%
在单链表中逆置n个节点,你可以采用迭代或递归的方式来实现。这里是一个基本的迭代方法:
1. 定义两个指针,一个指向当前节点(current),另一个指向前一个节点(prev)。初始时,prev设置为空,current设置为头节点。
2. 遍历整个链表:
a. 将当前节点的next指针存储在一个临时变量temp中,以便后续改变当前节点的next。
b. 将当前节点的next指向前一个节点(prev)。
c. 更新前一个节点(prev)和当前节点(current),将它们分别移动到下一个位置,即prev = current, current = temp。
3. 当遍历结束后,当前节点current会变成None(无),此时prev就是新的头节点。
以下是Python伪代码示例:
```python
def reverse_list(head):
prev = None
current = head
while current is not None:
next_temp = current.next
current.next = prev
prev = current
current = next_temp
return prev
```
阅读全文