数据结构 算法大全 编者：艾孜尔江
2
一、单链表............................................................................................................ 4
1.单链表反转................................................................................................. 5
2.找出单链表的倒数第 4 个元素................................................................. 7
3.找出单链表的中间元素............................................................................. 8
4.一个单链表，很长，遍历一遍很慢，我们仅知道一个指向某节点的指
针 curr，而我们又想删除这个节点。 ........................................................ 9
5.两个不交叉的有序链表的合并............................................................... 10
6.有个二级单链表，其中每个元素都含有一个指向一个单链表的指针。
写程序把这个二级链表展开称一级单链表。.......................................... 12
7.单链表交换任意两个元素（不包括表头）........................................... 14
8.判断单链表是否有环？如何找到环的“起始”点？如何知道环的长度？
...................................................................................................................... 15
9.判断两个单链表是否相交....................................................................... 17
10.两个单链表相交，计算相交点............................................................. 19
11.用链表模拟大整数加法运算 ................................................................. 20
12.单链表排序............................................................................................. 21
13.删除单链表中重复的元素..................................................................... 23
二、栈和队列...................................................................................................... 24
1.设计含 min 函数的栈，要求 min、push 和 pop 的时间复杂度都是 o(1)。
...................................................................................................................... 24
2.设计含 min 函数的栈的另解 .................................................................. 25
3.用两个栈实现队列................................................................................... 27
4.用两个队列实现栈................................................................................... 28
5.栈的 push、pop 序列是否一致 ............................................................... 30
6.递归反转一个栈，要求不得重新申请一个同样的栈，空间复杂度 o(1)
...................................................................................................................... 31
7.给栈排个序............................................................................................... 31
8..如何用一个数组实现两个栈.................................................................. 32
9..如何用一个数组实现三个栈.................................................................. 36
三、二叉树.......................................................................................................... 39
1.二叉树三种周游（traversal）方式： ..................................................... 40
2.怎样从顶部开始逐层打印二叉树结点数据........................................... 41
3.如何判断一棵二叉树是否是平衡二叉树............................................... 43
4.设计一个算法，找出二叉树上任意两个节点的最近共同父结点，复杂
度如果是 O(n
2
)则不得分。 ........................................................................ 44
5.如何不用递归实现二叉树的前序/后序/中序遍历？ ............................ 47
6.在二叉树中找出和为某一值的所有路径............................................... 50
7.怎样编写一个程序，把一个有序整数数组放到二叉树中？............... 51
8.判断整数序列是不是二叉搜索树的后序遍历结果............................... 51
9.求二叉树的镜像....................................................................................... 52
10.一棵排序二叉树（即二叉搜索树 BST）， 令 f=(最大值+最小值)/2，
设计一个算法，找出距离 f 值最近、大于 f 值的结点。复杂度如果是
