Question

顺序存储的线性表有n个元素,该线性表的逆置算法怎么写?

Answer 1

设线性表中有n个元素，从第1个元素开始向后遍历，直到第n/2个元素为止，当遍历到第i个元素时，将它与第n-i+1个元素互换位置，比如第1个元素就和第n-1+1=n个元素互换位置。算法分析：只需遍历n/2个元素，因此时间复杂度o(n)，属于线性时间复杂度。
空间占用方面，只在交换时用到一个临时存贮空间，因此为o(1)，属于常量空间复杂度