顺序表
无论是偶数个还是奇数个
都可以是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)
网友评论