设计一个算法,将链表中所有结点的链接方向“原地”逆转,即要求仅利 用原表的存储空间,换句话说,要求算法的空间复杂度为O(1)。
时间: 2024-05-02 20:21:18 浏览: 116
写一个算法将一单链表逆置。要求操作在原链表上进行。
算法步骤如下:
1. 定义三个指针,分别指向当前结点(cur)、当前结点的前一个结点(pre)和当前结点的后一个结点(next)。
2. 将当前结点的后一个结点保存在next中。
3. 将当前结点的next指向pre。
4. 将pre指向cur。
5. 将cur指向next。
6. 重复步骤2-5,直到cur指向尾结点为止。
7. 将头结点的next指向pre。
完整代码如下:
```python
def reverse_linked_list(head):
if not head or not head.next:
return head
pre = None
cur = head
while cur:
next = cur.next
cur.next = pre
pre = cur
cur = next
head.next = pre
return head
```
时间复杂度为O(n),空间复杂度为O(1)。
阅读全文