数组和链表的区别是什么
数组与链表是两种不同的数据存储方式。链表的特性是在中间任意位置添加元素、删除元素都非常地快，不需要移动其他的元素。通常对于单链表而言，链表中每一个元素都要保存一个指向下一个元素的指针；而对于双链表，每个元素既要保存一个指向下一个元素的指针，还要保存一个指向上一个元素的指针；循环链表则在最后一个元素中保存一个指向第一个元素的指针。
数组是一组具有相同类型和名称的变量的集合，这些变量称为数组的元素，每个元素都有一个编号，这个编号称为数组的下标，可以通过下标来区别并访问这些元素，数组元素的个数也称为数组的长度。。
具体而言，数组和链表的区别主要表现在以下几个方面：
（1）逻辑结构。数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况，即在使用数组之前就必须对数组的大小进行确定。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。数组中插入、删除数据项时，需要移动其他数据项。而链表采用动态分配内存的形式实现，可以适应数据动态地增减的情况，需要时可以用new/malloc分配内存空间，不需要时用delete/free将已分配的空间释放，不会造成内存空间浪费，且可以方便地插入、删除数据项。
（2）内存结构。（静态）数组从栈中分配空间，对于程序员方便快速，但是*度小。链表从堆中分配空间，*度大，但是申请管理比较麻烦
（3）数组中的数据在内存中是顺序存储的，而链表是随机存储的。数组的随机访问效率很高，可以直接定位，但插入、删除操作的效率比较低。链表在插入、删除操作上相对数组有很高的效率，而如果要访问链表中的某个元素，那就得从表头逐个遍历，直到找到所需要的元素为止，所以链表的随机访问效率比数组低。
（4）链表不存在越界问题，数组有越界问题。数组便于查询，链表便于插入删除，数组节省空间但是长度固定，链表虽然变长但是占了更多的存储空间
所以，由于数组存储效率高、存储速度快的优点，如果需要频繁访问数据，很少插入删除操作，则使用数组；反之，如果频繁插入删除，则应使用链表。
找出单链表中的倒数第k个元素
为了找出单链表中的倒数第k个元素，最容易想到的方法是首先遍历一遍单链表，求出整个单链表的长度n，然后将倒数第k个，转换为正数第n-k个，接下来遍历一次就可以得到结果。但是该算法需要对链表进行两次遍历，第一次遍历用于求解单链表的长度，第二次遍历用于查找正数第n-k个元素。
第二种方法，如果沿从头至尾的方向从链表中的某个元素开始，遍历k个元素后刚好达到链表尾，那么该元素就是要找的倒数第k个元素。根据此性质，设计以下算法：从头结点开始，依次对链表的每一个节点元素进行这样的测试，遍历k个元素，查看是否到达链表尾，直到找到那个倒数第k个元素为止。此种方法将对同一批元素进行反复多次的遍历，对于链表中的大部分元素而言，都要遍历k个元素，如果链表长度为n，该算法时间复杂度为O(kn)级，效率太低。
存在一种高效的方式，只需要一次遍历即可查找到倒数第k个元素。由于单链表只能从头到尾依次访问链表的各个结点，所以如果要找链表的倒数第k个元素，也只能从头到尾进行遍历查找。在查找过程中，设置两个指针，让其中一个指针比另一个指针先前移k步，然后两个指针同时往前移动。循环直到先行的指针值为NULL时，另一个指针所指的位置就是要找的位置。
如何检测一个较大的单链表是否有环
单链表有环是指单链表中某个结点的next指针域指向的是链表中在它之前的某一个结点，这样在链表的尾部形成一个环形结构。检测单链表是否有环，一般有以下几种方法。
方法一：定义一个指针数组，初始化为空指针，从链表的头指针开始往后遍历，每次遇到一个指针就跟指针数组中的指针比较，若没有找到相同的指针，说明这个结点时第一次访问，还没有形成环，将这个指针添加到指针数组中去。若在指针数组中找到了同样的指针，说明这个节点已经被访问过了，于是就形成了环。
方法二：定义两个指针 fast与 slow，两者的初始值都指向头，slow每次前进一步，fast每次前进两步，两个指针同时向前移动，快指针每移动一次都要跟慢指针比较，直到当快指针等于慢指针为止，就证明这个链表是带环的单向链表，否则证明这个链表是不带环的循环链表（fast先行到达尾部为NULL，则为无环链表）
方法三：通过使用STL库中的map表进行映射。首先定义map<node* , int> m；将一个node * 指针映射成数组的下标，并赋值为一个int类型的数值。然后从链表的头指针开始往后遍历，每次遇到一个指针p，就判断m[p] 是否为0.如果为0，则将m[p]赋值为1，表示该结点时第一次访问；而如果m[p]的值为1，则说明这个结点已经被访问过一次了，于是就形成了环。
判断两个单链表（无环）是否交叉
单链表相交是指两个单链表存在完全重合的部分（注意，不是交叉到一个点）。判断两个单链表是否交叉，一般有两种方法：
（1）将则两个链表首尾相连，然后检测看这个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点
（2）利用链表相交的性质，如果两个链表相交，那么两个链表从相交点到链表结束都是相同的结点，必然是Y字形，所以判断两个链表的最后一个结点是不是相同即可。即先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交，这时记下两个链表的长度length，再遍历一次，长链表结点先出发前进（LengthMax-LengthMin）步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。
删除单链表中的重复结点
一个没有排序的链表，如list = { a,1,x,b,e,f,f,e,a,g,h,b,m}，去掉重复项，并保留原顺序，以上链表去掉重复项后为 newlist = { a,1,x,b,e,f,g,h,m }
方法一：递归法求解（效率低）
方法二：使用hash法，具体过程如下。
（1）建立一个hash_map，key为链表中已经遍历的结点内容，开始时为空。
（2）从头开始遍历链表中的结点
- 如果结点内容已经在hash_map中存在，则删除此结点，继续向后遍历。
- 如果结点内容不在hash_map中，则保留此结点，将结点内容添加到hash_map中，继续向后遍历。
如何在不知道头指针的情况下将结点删除
在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删除？若可以，其时间复杂度各为多少？
分别讨论3种链表的情况。
（1）单链表。当知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前驱。因此无法删除该结点
（2）双链表。由于这一的链表提供双向链接，因此根据已知结点可以查找到其直接前驱和直接后继，从而可以删除该结点。其时间复杂度为O(1)
（3）单循环链表。根据已知结点位置，可以直接得到其直接后继，又因为是循环链表，所以可以通过查找得到p结点的直接前驱。因此，可以删除p所指的结点。其时间复杂度应为O(n)