首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

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

2012-12-21 
关于链表追赶--链表中环的问题关于环的问题,介绍几个个经典的题目:1.求链表倒数第k个结点?最经典,最常见的

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

关于环的问题,

介绍几个个经典的题目:

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个长度,然后两个链表同时开始向下遍历,并进行比较,第一个相等的即为两个链表相交的首个交点。

热点排行