[TOC]
拿到一个问题,我们的解题步骤可以归纳为:
审题
归纳出题目的特点,确定使用的数据结构
从该数据结构的特点出发,结合题目的特点,寻找算法思路
例如将顺序表进行逆置的问题,审题后,关键词是 顺序表 和 逆。顺序表就要想到根据 index 在 $O(1)$ 时间内获取值和长度已知的特性;逆置就要想到栈的特性。
还要考虑,是对时间复杂度要求高,还是空间复杂度要求高。
编码
返回值是什么?
输入输出是什么?
考虑边界
……
位置互换,利用 index 进行逆置
头插法逆置单链表
快慢指针
链表节点最有价值的是节点值,而不是整个节点,这是个可以变通的地方,在不依赖前驱节点删除链表节点的时候,就用到了这个思想
链表真正可以有所作为的地方,在于链表的头部,链表头部的操作,复杂度最低