链表总结

1.快速找到未知长度单链表的中间节点

a.初级算法：

从头遍历到末尾，再次从头遍历到中间处。O（L+L/2) =O（3L/2）

b.高级算法：

利用快慢指针原理：设置两个指针fast 和mid，都指向单链表的头节点。其中fast的移动速度是mid的2倍。当fast指向末尾节点的时候，mid正好就在中间了。O(L/2)

2.判断链表中是否有环

利用快慢指针原理，最后快慢指针相撞。

1. 有环时求环的长度 记录碰撞点P，slow、fast指针从该点出发，再次碰撞所走过的操作数就是环的长度s。 2. 找出环的连接点 有定理：碰撞点p到连接点的距离=头指针到连接点的距离，因此，分别从头结点，碰撞点开始走（相同的速度），相遇的地方就是连接点。 证明：

3. 求带环链表的长度 问题2中已经求出连接点距离头指针的长度，加上问题1中求出的环的长度，二者之和就是带环单链表的长度

3.判断两个无环链表是否相交，并找出相交点

a.转换为判断是否有环。将第一个链表的表尾部指向第二条链表的头部，再从第二个链表的头部进行遍历（如果有环，那么第二条的头节点就一定在环上）。

b.遍历两条链表，并判断最后一个节点是否相等，因为，如果相交，那么最后一个节点一定相同。

c.判断两个链表中是否存在地址一致的节点，就可以知道是否相交了。可以对第一个链表的节点地址进行hash排序，建立hash表，然后针对第二个链表的每个节点的地址查询hash表，如果它在hash表中出现，则说明两个链表有共同的结点。这个方法的时间复杂度为：O(max(len1+len2)；但同时还得增加O(len1)的存储空间存储哈希表。这样减少了时间复杂度，增加了存储空间。以链表节点地址为值，遍历第一个链表，使用Hash保存所有节点地址值，结束条件为到最后一个节点（无环）或Hash中该地址值已经存在（有环）。

判断出两个链表相交后，找出其相交点。

法1：假设第一条和第二条链表的长度为len1，len2，然后找出较长的链表，并让其从|len1- len2|，开始遍历，逐个比较两个链表的值。 法2：将两个链表压栈，并比较两个栈出来的数据，直到两个数据不同时，就可以判断相交点。

问题的延伸： 如果原来的两个链表中有环怎么处理？ a.创建第一个链表的地址hash，直到所有节点都存入（终结条件就是添加新的hash时，hash表中已经存在了）。遍历第二个链表，并hash，判断是否在表中。 b.分三种情况：两条head都不在环上，都在环上，有一个在环上，这三种方式都可以用快慢指针进行判断。

3.用两个栈实现链表