设计算法将单链表L就地逆置
时间: 2024-05-09 17:16:45 浏览: 95
对单链表实现就地逆置算法
4星 · 用户满意度95%
单链表的就地逆置可以通过修改节点的指向来实现。具体算法如下:
1. 定义三个指针:prev、curr、next,分别指向前一个节点、当前节点和后一个节点。
2. 初始化prev为NULL,curr为L的头节点。
3. 遍历单链表,重复以下步骤:
1. 将next指针指向curr的下一个节点。
2. 将curr的下一个节点指向prev。
3. 将prev指针指向curr。
4. 将curr指针指向next。
4. 最后将L的头节点指向prev,完成就地逆置。
下面是具体的实现代码:
```python
def reverse_list(head):
prev = None
curr = head
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
head = prev
return head
```
需要注意的是,本算法的时间复杂度为O(n),其中n为单链表的长度。
阅读全文