关于链表追赶--链表中环的问题

关于环的问题，

介绍几个个经典的题目：

1.求链表倒数第k个结点

 

最经典，最常见的解法就是，设置两个指针p1，p2，一开始分别指向头结点,首先p2先移动k个节点，之后开始p1，p2每次移动1个节点，直到p2达到最后一个节点位置，那么p1指向的就是倒数第k个节点。

 

不过这种解法主要是针对单链表，且链表中不存在环的，如果是双向链表，或者是存在环的链表呢？

在判断是否在最后一个节点上就会出现问题了，ps.循环链表中判断最后一个节点就需要查看其pre指针指向的节点是否是刚才遍历过的节点。对于存在环的节点判断最后一个节点就有点麻烦了：

 

判断一个链表是否存在环

 

环的定义如上：

 

定义两个指针，开始的时候分别指向head，之后p1每次移动一个节点，p2每次移动两个节点，如果p2遇到null 的时候，不存在换否在p1，p2肯定在环内相遇。当p1==p2的时候，退出，存在环

 

判断两个链表是否相交

 

对于这个问题，这里的相交不会存在“X”的相交，而是“Y”形状的相交。

 

解法一

使用两个for循环来同时遍历两个数组，来发现首个相同的节点，不过时间复杂度会达到O(M*N)

 

解法二

使用hash表存储第一个链表的所有元素，通过遍历第二个链表，检查是否相同的节点在hash表中，有的话则说明两个链表有相同的子序列，否则就没有。时间复杂度为O(M+N),空间复杂度为O(M),不是很理想

 

解法三

如果链表相交则链表的最后一个节点一定是相同的，我们只需要判断最后一个节点是否相同即可。时间复杂度为O(M+N),空间复杂度减少到O(1)

 

当然上述几种方法都是建立在无环链表的基础之上的。

所以总结如下解决办法：

1.先判断带不带环
2.如果都不带环，就判断尾节点是否相等
3.如果都带环，判断第一个链表上是否存在环时---俩指针相遇（在环中相遇）的那个节点，在不在另一条链表上。如果在，则相交，如果不在，则不相交。

 

判断一个存在环的链表的环的第一个节点

 

在网上看到一个解决办法，类似龟兔赛跑的原理，定义两个指针p1，p2。p2一直向前走，p1，也是向前走，每走一步检查下是否赶上p2，如果赶上了，就从头再跑，此时p2向前走一步，如果没赶上，则继续往前走，此时p2停下等待，如此循环，直到，p1==p2->next,此时p2计时所求的点。

 

求两个相交链表的首个交点

 

解法1：

使用两个for循环来同时遍历两个数组，来发现首个相同的节点，不过时间复杂度会达到O(M*N)

 

解法2

每个节点添加一个vist访问标志位，来表示已经访问过的节点。首先遍历第一个链表，将访问位置true，然后遍历第二个链表，当发现vist的位true时，则这个节点就是两个链表相交的首个交点。时间复杂度为O（M+N）

 

解法3：

首先求出两个链表的长度c,d;

求出f=abs(c-d);

较长的那个链表首先遍历f个长度，然后两个链表同时开始向下遍历，并进行比较，第一个相等的即为两个链表相交的首个交点。