判断链表是否有环

如何判断一个链表是否有环？

1.png

• 首先创建两个指针1和2，同时指向这个链表的头结点。然后开始一个大循环，在循环体中，让指针1每次向下移动一个节点，让指针2每次向下移动两个节点，然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环。

判断两个链表是否交叉并找出交点

2.png

1. 判断是否交叉
   先遍历第一个链到它的尾部，然后将尾部的next指针指向第二个链表，这样两个链表就合成了一个链表，判断原来的两个链表是否相交也就转变成了判断新的链表是否有环的问题：即判断单链表是否有环？

   
   3.gif

这种方法可以判断两个链表是否相交，但是不容易找出他们的交叉点

2. 找出交点
   仔细研究两个链表，如果它们相交的话，那么它们最后的一个交点一定是相同的，否则不相交的。因此判断两个链表相交就很简单了，分别遍历到两个链表的尾部，然后判断它们是否相同，如果相同，则相交；否则不相交

   
   4.gif
   

   判断出两个链表相交后。假设第一个链表长度为len1,第二个为len2,然后找出长度最长的，让长度较长的建表先前移动|len1-len2|，然后再开始遍历两个链表，判断节点是否相同即可。