summary.md

Summary

[TOC]

解题思路

拿到一个问题，我们的解题步骤可以归纳为：

1. 审题

   1. 归纳出题目的特点，确定使用的数据结构

   2. 从该数据结构的特点出发，结合题目的特点，寻找算法思路

      例如将顺序表进行逆置的问题，审题后，关键词是 顺序表 和 逆。顺序表就要想到根据 index 在 $O(1)$ 时间内获取值和长度已知的特性；逆置就要想到栈的特性。

      还要考虑，是对时间复杂度要求高，还是空间复杂度要求高。

2. 编码

   1. 返回值是什么？
   2. 输入输出是什么？
   3. 考虑边界
   4. ……

ArrayList

• 位置互换，利用 index 进行逆置

LinkList

• 头插法逆置单链表
• 快慢指针
• 链表节点最有价值的是节点值，而不是整个节点，这是个可以变通的地方，在不依赖前驱节点删除链表节点的时候，就用到了这个思想
• 链表真正可以有所作为的地方，在于链表的头部，链表头部的操作，复杂度最低