链表有环问题_链表有多个环

判断一个链表是否有环

解析：如果链表有环，则设置一个指针，该指针会一直循环下去。我们可以设置两个指针，一个一次走一步，一个一次走两步，如果有环最终两者会相遇，否则每次走两步的指针最先走到链表尾部。如下图：

延伸：判断两个链表是否相交
给出两个单向链表的头指针，比如L1，L2，判断这俩个链表是否相交。
1、为了简化问题，我们假设俩个链表均不带环。

（1）我们可以遍历两个链表，判断他们最后指向的节点是否相同，相同则相交；

（2）将一个指针的头结点跟另一个指针的尾节点相连接，判断新链表是否有环，如图

2、如果链表可能有环呢?

这种情况有两种：一个链表有环、另一个没环；是否相交也有两种情况。这共有4种情况，如果两个链表都有环而且不想交，则使用两个指针无法判断是否相交，而且不会终止，会死循环。

我们可以先判断两个链表是否都有环，如果仅有一个有环，则可以通过两个指针，一个单步走，一个双步走，类似最前的方法。

如果两个都有环，我们只能判断他们中是否有节点相同。3中详述。
3、如果需要求出俩个链表相交的第一个节点列?

（1）显然前面的方法都不行。有一个最笨的办法，就是遍历一个链表，对其每一个节点，遍历另外一个链表，查看是否相同，则第一个相同的节点便是所求。若链表长度分别为m、n，则时间复杂度为O(mn);

（2）若要缩小时间复杂度，则需要牺牲空间。我们用hash表来解决，如果事先知道链表的长度，则先遍历短链表，将每个节点存入哈希表中，然后再遍历长链表，第一个在hash表中找到的节点便是所求，时间复杂度为O(m+n)，空间复杂度最优为O(min(m, n))。

（3）如果对时间和空间复杂度都要求很高呢？

我们仔细观察上面相交的链表，如果同时从两个链表开始往后走，每走一步判断节点是否相同，当走到相同节点的时候便得所求。

问题来了，如果链表长度不同，如何解决呢？我们可以通过一次遍历，找到链表的长度，比如d1、d2，如果d2较大，那么我们先从链表L2走，走几步呢，steps=d2 - d1。

走steps步数之后，剩下L2的节点数和L1的节点数是相同的。然后同时往后走，没走一步判断一步，直到为相交节点结束。