关于链表追赶--链表中环的问题
关于环的问题,
介绍几个个经典的题目:
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个长度,然后两个链表同时开始向下遍历,并进行比较,第一个相等的即为两个链表相交的首个交点。