一、已知一个单链表p，如何判断它是否存在环。
定义两个指针fast和slow，均初始化为p，fast一次走2步，slow一次走1步，如果两个指针在q处相遇，那么存在环，相遇的地方一定是slow一圈没有走完，fast走完一圈，在走第二圈的时候。
扩展：如何知道环的长度？如何找出环的连接点在哪里？带环链表的长度是多少？
记录q的位置，继续走直到再碰上q那么之间走过的距离就是环的长度；
slow从p重新开始走，fast从q开始走，每次都是走1步，相遇的地方就是环的连接点；
知道环的长度和slow从p到连接点的长度相加就是链表的长度；
二、已知两个没有环的链表p和q，如何判断两个链表是否相交。
方法一：将第一个链表中的节点根据其地址进行hash，建立hash表，然后对第二个链表每个节点地址查询hash表，如果某个节点在hash表中出现，那么说明第二个链表和第一个链表有公共节点。该方法时间复杂度为o(length1+length2)；但是它需要o(length1)的存储空间来存储哈希表。
方法二：将第二个链表的头节点链接到第一个链表的最后，遍历第二个链表，如果在此过程中又回到起始点即q，那么说明这两个链表相交。最后注意要恢复原来的状态。去掉第一个链表到第二个链表头节点的链接。时间复杂度为o(length1+length2)。
方法三：如果两个没有环的链表相交，那么在这个相交节点之后的每一个节点都是两个链表所共有的，这样，最后一个节点一定是共有的，所以我们只要看两个链表最后一个节点是否相同即可。时间复杂度o(length1+length2)。
如何确定第一个相交节点的位置：
设较长链表长度为maxLength，较短链表长度为minLength，定义两个指针pTemp=p和qTemp=q（假设pTemp更长），让pTemp先走maxLength-minLength步，然后pTemp和qTemp再同时走，直到找到某个结点使得pTemp == qTemp，该节点就是第一个相交节点位置。
扩展：如果链表可能存在环，那么如何判断？
如果两个链表都没环，同原算法；如果一个有环，一个没有，那么必然不相交；如果两个链表都有环，判断一个链表环上的任一点是否在另一个链表上，如果是，那么两个链表相交，反之不相交。所以此问题关键是判断一个链表中是否存在环。