数据结构与算法基础

1、说一下几种常见的排序算法和分别的复杂度
O(n2) : 冒泡排序、选择排序、插入排序、希尔排序
O(nlogn) : 快速排序、归并排序、堆排序
O(n) : 桶排序 O(d(n+r)): 基数排序
快速排序的效率最高，但是复杂度的稳定性不高，如果初始值选的不好，会造成复杂度上升至O(n2)，为避免这种情况可以使用堆排序，但是这俩种排序方式都是不稳定的，相同复杂度，稳定排序的是归并排序 ，辅助空间大
2、什么是跳表？
跳表是针对链表查询的优化方式，是基于有序链表的拓展，原本的链表的查询效率是O(n)的，跳表是有多层组成，每一层都是一个有序的链表，这样会造成链表的插入和删除很麻烦，但是可以让检索的时间接近线性（Ologn)

3、如何确认一个链表有环？进一步，确认环的位置。
取指向链表头结点的节点两个，A、B，A每次走两步，B每次走一步，循环执行远大于链表可能长度的次数，如果两者期间再次重合，设重合于C节点，说明有环
环的位置：

这个问题就更靠近脑筋急转弯的方向了。首先想到，如果还是p1和p2一起跑圈，那仍然会发生很多次相遇，但是这个相遇跟起点并无关系，想求出入口不可能。
那我们就分析一下，p1和p2相遇的时候到底发生了什么。在示意图中，假设p1和p2在P点第一次相遇。从环路入口到P点的距离为x，从P点到环路入口的另一段的距离为y。
那么显然，第一次相遇的时候，p1走过的总长度为x+z。那p2呢？我们首先假设p2比p1只多跑了一圈（方便理解，但并不影响最后结论，下面再证明所有的情况）。那么容易得到，p2走过的总长度为z+x+y+x。这个结论很显然也是表明p2比p1多跑了一圈（一圈的长度就是x+y，与前面的分析吻合）。由于p2的速度是p1的两倍，很容易得到一个结论：z+x+y+x = 2 * (x+z)。也就是z = y。也就是说，相遇的点离环路入口的距离与链表直道的长度一样。
呵呵，得到这个结论似乎就离我们的答案很近了：如何才能找到这个入口位置呢？显然，让一个指针从相遇的P点出发，另外一个指针从链表头出发，以相同的速度前进，那么它们必然会在O点也就是环路入口相遇！来自 http://blog.chinaunix.net/uid-28533920-id-3837916.html

4、如何遍历一棵二叉树？
先、中、后序遍历，层次遍历
非递归的代码样例
5、倒排一个LinkedList。
这个是将链接翻转，然后尾节点变头节点就可以了
6、hashSet的实现方式
基于hashMap实现，hashMap是通过哈希算法来保证检测key的唯一性，并通过拉链法来处理碰撞问题