---

1. 两个有序链表的合并：设两个有序链表分别为L1和L2，先用两个指针分别遍历这两个链表，并且每次读取两个链表中元素的值，将较小的值插入到新的链表L中，如果其中一个链表遍历完毕，则另一个链表中剩下的元素就可以直接接在L的表尾。

2. 求链表中倒数第k个结点：①可以使用栈，将链表中全部元素入栈，在出栈时选择第k个结点。②设置快慢指针，其中快指针比慢指针多走k-1步，那么当快指针走到终点的时候，慢指针就指向了倒数第k个结点。

3. 括号匹配：括号匹配算法用栈来实现，给定一组括号，如果是左括号就直接入栈，如果是右括号就从栈顶弹出一个元素，如果匹配则继续，如果不匹配则直接返回false，最后括号都遍历完毕后再检查栈中是否还有元素，如果没有则说明匹配成功，否则说明匹配失败。

4. 哈夫曼树：先从所有的结点中选出两个值最小的结点，构成一棵树，然后再将这两个结点值之和与其他结点进行比较，直到所有的结点都连接在一棵树上为止。

5. 二分查找：二分查找只适用于排好序的情况，先用两个指针分别指向数组的首部和尾部，然后执行循环的条件是首部指针的位置小于尾部指针的位置，每次找到首尾指针的中心位置然后与要查找的元素（设为x）比较，如果比x要大，则从数组的前一半中继续寻找，如果比x要小，则从数组的后一半中寻找。如果循环结束后还没有找到说明数组中没有这个元素，时间复杂度为O(logn)。

6. 冒泡排序：设排序序列记录的元素为n，进行n-1次遍历，每次遍历从开始位置依次往后比较前后相邻元素，这样较大的元素后移，n-1次遍历结束后，序列有序，平均时间复杂度为O(n^2)。

7. 简单选择排序：设排序序列的记录个数为n，进行n-1次选择，每次在n-i+1个记录中选择关键字最小的记录作为有效序列中的第i个记录，平均时间复杂度为O(n^2)。

8. 直接插入排序：将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数加1的有序表，第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。平均时间复杂度为O(n^2)。

9. 归并排序：归并排序是分治法的一个典型应用，主要思想是将待排序列分为两部分，对每部分递归...