二分查找是一种在有序列表中查找元素的高效方法，时间复杂度（logN），二分查找思路和时间都比较简单，但是实际问题中的细节不可忽视。

3.1 搜索插入位置

LeetCode No.35

2.1 快速排序

题目描述：实现快速排序

思路：采用交换法，选第一个数为基准数pivot，在pl <= pr的前提下，指针pl从基准数+1的位置向右走，直到碰到比pivot大的数，指针pr从最右边向左走，直到碰到比pivot小的数，交换arr[pl], arr[pr]，循环结束时pr = pl - 1，将基准数和pr交换。递归调用对基准数位置两边的区间调整。

双指针通常用在有序数组，链表的数据结构上，根据题目条件移动对应的指针。比如判断子串、链表是否有环的问题。

1.1 最长子串

LeetCode No.524

题目描述：给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串 输入: s = “abpcplea”, d = [“ale”,“apple”,“monkey”,“plea”] 输出: “apple”

6.1 栈

6.1.1用两个栈实现一个队列

LeetCode No.232

题目描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）：

思路： 两个栈一个栈做队头（出元素），另一个栈做队尾（入元素）

4.1 根据前序与中序序列构造二叉树

LeetCode No.105

问题描述：根据一棵树的前序遍历与中序遍历构造二叉树。

思路：根据二叉树的前序和中序（或后序和中序）的序列可唯一构造一棵二叉树，必须要有中序。前序遍历的第一个为根节点，找到根节点在中序中的位置，中序左边的节点都是根节点的左子树，右边的同理，然后可以用递归的方式求解。

3.1 删除单向链表倒数第n个节点

LeetCode No.19

问题描述：删除单向链表倒数第n个节点（只遍历一次） Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5]

思路：两个指针，p1先走n步，然后p1和p2再一起走，当p1到链表结尾，p2就是要删除的节点。注意处理可能删除的是头结点（n=length）或者不需要删除（n>length）的情况。 可以通过增加一个虚拟的头节点，避免对头节点的特殊处理。