线性表逆置

顺序表

无论是偶数个还是奇数个
都可以是i<j时循环就一直进行下去
否则跳出循环

没有必要分两套代码
一套代码就够了

顺序表的逆置

单链表逆置
一般逆置
会从p指针所指结点的后继结点 开始
一直到q指针所指结点 结束 之间的所有结点

单链表的逆置

删除结点 但是不free 然后把这个结点插入

到p->next等于q 就结束了

顺序表

让i 扫描 前k个位置 并交换
当k大于 表长的一半的时候
条件 i<j 来约束
否则有些元素多次交换

前k个(0~k-1) 逆置k个
前n个(0~n-1) 逆置k个
逆置两次

另一种想法 是前k个整体逆置

本章开头留的题 就可以解决了

0~p-1元素 逆置p个
p~n-1元素 逆置n-p个
0~n-1元素 逆置n个

第一问 思想
先逆置前半段
再逆置后半段
最后逆置整个

第三问
三个并列循环 都是线性级的
时间复杂度 O(n)

在保存序列的数组中折腾
没有额外的存储空间消耗
消耗的空间是常量
数组的空间不变
因此
空间复杂度O(1)