数据结构面试题总结

数据结构面试题总结

数据结构面试题

• • 如何从链表中删除重复数据
  • 如何找出单链表中的倒数第k个元素
  • 如何从尾到头输出单链表
  • 如何寻找单链表的中间结点
  • 如何检测一个链表是否有环
  • 如何在不知道头指针的情况下删除指定结点
  • 如何判断两个链表相交
  • 如何判断两个链表相交的第一个结点
  • 如何选择排序
  • 如何插入排序
  • 如何冒泡排序
  • 如何归并排序
  • 如何快速排序
  • 如何希尔排序
  • 如何堆排序

如何从链表中删除重复数据

1. 遍历链表，把遍历到的值存储到Hashtable中，在遍历的过程中，若当前访问的值在Hashtable中是否存在，说明这个数据是重复的。优点 ：时间复杂度低，缺点：在遍历过程中需要额外的存储空间来存储遍历过的值
2. 使用双循环，在外循环中正常的进行遍历，在内循环中从当前结点进行遍历，若与当前结点值相同，3则删除这个重复结点。优点：不需要额外的空间进行存储，缺点：时间复杂度高。

如何找出单链表中的倒数第k个元素

1. 遍历单链表，求出链表的长度n，第二次遍历找到n-k个元素。
2. 从头到尾遍历k个元素，若正好是最后一个结点，说明是倒数第k个元素。
3. 用两个指针，前面的指针比后面的指针多走k-1步，两个指针同时向前移动，循环到前面的指针为null，说明后面的指针为倒数第k个元素。

如何从尾到头输出单链表

1. 从头到尾遍历链表，将结点压入栈中，遍历结束后，在从栈顶输出结点。
2. 递归实现，每次访问先输出它后面的结点，再输出该结点自身。

如何寻找单链表的中间结点

1. 先求解单链表的length，然后遍历length/2的距离。需要遍历两次链表。
2. 两个指针同时遍历，一个每次遍历一步，一个每次遍历两步，当第二个指针走到链表尾部结点时，第一个就正好在链表中间结点附近。判断第一个指针的长度，是奇数则第二个指针为中间结点。是偶数则第二个指针结点和下一个结点为中间结点。

如何检测一个链表是否有环

两个指针，一个指针每次走一步，另一个指针每次走两步，当两个指针相等时，说明链表是环。

如何在不知道头指针的情况下删除指定结点

1. 如果删除的结点是尾结点，则不能删除，无法保证前驱结点的next为空。
2. 如果删除的结点不是尾结点，则将结点的值与后继结点的值进行交换，删除后继结点。

如何判断两个链表相交

分别遍历两个链表，如果尾结点相同，证明相交

如何判断两个链表相交的第一个结点

1. 判断两个链表相交。
2. 分别计算两个链表的长度，len1和len2（len1>len2）先将长链表走（len1-len2）步，之后同时遍历两个链表，遇到相同的结点时，证明是两个链表相交的第一个结点。

如何选择排序

对于给定的一组记录，经过第一轮比较得到最小的记录，然后将该记录与第一个记录进行交换；接着对除了第一个记录外的记录进行比较，将第二个最小的记录与第二个记录交换；重复此过程，直到比较最后一个记录为止。

如何插入排序

假设第一个记录是有序序列，从第二个记录开始，按照记录的大小插入有序记录中，直至最后一个记录插入有序序列为止。

如何冒泡排序

（从小到大排序）从第一个记录开始依次对相邻的两个记录进行比较，将最小的交换到前面，重复该过程直到进行比较的记录只剩一个为止。

如何归并排序

归：递归，将数组进行折半分离
并：将分开的数据按照一定顺序放在一个数组中，直到并成一个大的数组中为止。

如何快速排序

通过一趟排序后，将原序列分为两部分，其中前一部分的所有记录均比后一部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。

如何希尔排序

先将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个待排序序列”基本有序后“，最后在对所有元素进行一次直接插入排序。

如何堆排序

初始时把记录看作二叉树，将其调整为大顶堆，接着进行前一个元素调整为大顶堆，重复该过程，直至剩下一个元素为止，此时可得到一个有序序列。