设计一个算法,将线性表L,如L顺序存储,则将线性表中的元素就地逆转。(存储空间复杂度为O(1))。
时间: 2024-10-11 21:09:53 浏览: 24
12.zip_清除线性表_清除线性表L_顺序表
设计一个就地逆转线性表的算法(即原地操作,不需要额外的存储空间),可以采用双指针法。这里给出一种简单的Python实现:
```python
def reverse_list_in_place(L):
# 定义两个指针,一个指向列表头部(start),一个指向尾部(end)
start = 0
end = len(L) - 1
while start < end:
# 交换当前位置的元素
L[start], L[end] = L[end], L[start]
# 移动指针
start += 1 # 遍历到下一个位置
end -= 1 # 指向倒数第二个位置
# 示例:
L = [1, 2, 3, 4, 5]
reverse_list_in_place(L)
print(L) # 输出:[5, 4, 3, 2, 1]
```
这个算法的时间复杂度为O(n),其中n是线性表的长度,因为每个元素都被访问一次。由于整个过程都在原数组上进行操作,所以空间复杂度为O(1)。
阅读全文