设计⼀个算法,将链表中所有结点的链接⽅向“原地”逆转,即要求仅利⽤原表的存储空间,换句话说,要求算法的空间复杂度为 O(1)。
时间: 2024-09-22 20:08:32 浏览: 67
Java数据结构与算法-单链表 新浪,腾讯面试题详解
设计一个原地反转链表的算法通常采用迭代的方式,不需要额外的数据结构。这里是一个步骤描述:
1. 定义三个指针:prev(前一个节点)、current(当前节点)和nextTemp(临时存储下一个节点的引用)。
2. 初始化 prev 和 current 分别指向 null 和头节点。
3. 当 current 不为空时,执行以下操作:
a. 将 current 的 next 指针暂时保存到 nextTemp 中。
b. 更新 current 的 next 指向 prev。
c. 将 prev 移动到 current。
d. 将 current 移动到 nextTemp (因为之前已经保存了下一个节点的位置)。
4. 当遍历完整个链表后,prev 就会成为新的头节点。
以下是 Python 代码实现示例:
```python
def reverseList(head):
prev = None
current = head
while current is not None:
next_temp = current.next
current.next = prev
prev = current
current = next_temp
return prev # 返回新头节点
```
阅读全文