前言
链表实际上是线性表的链式存储结构,与数组不同的是,它是用一组任意的存储单元来存储线性表中的数据,存储单元不一定是连续的,且链表的长度不是固定的,链表数据的这一特点使其可以非常的方便地实现节点的插入和删除操作。
链表的每个元素称为一个节点,每个节点都可以存储在内存中的不同的位置,为了表示每个元素与后继元素的逻辑关系,以便构成“一个节点链着一个节点”的链式存储结构,除了存储元素本身的信息外,还要存储其直接后继信息。
因此,每个节点都包含两个部分,第一部分称为链表的数据区域,用于存储元素本身的数据信息,可以用data表示,它不局限于一个成员数据,也可是多个成员数据,第二部分是一个结构体指针,称为链表的指针域,用于存储其直接后继的节点信息,可以用next表示,next的值实际上就是下一个节点的地址,当前节点为末节点时,next的值设为空指针。
链表代码可以用下述代码表示。
1 | private class Node{ |
正文
我们来看一下关于链表的一些经典问题。
- 如何判断一个链表是否有环?如果有环,如何找到环入口节点?
- 如何判断两个链表是否相交?
对于上述问题,我们分别来看一下。
是否环链表
对于第一个问题,我们可以采用“快慢指针”的方法来解决。如下图:
思路:(结论1)设置快慢指针,都从链表头出发,快指针每次走两步,慢指针一次走一步,假如有环,一定相遇于环中某点。
(结论2)接着让两个指针分别从相遇点和链表头出发,两者都改为每次走一步,最终相遇于环入口。
我们来看下这两个结论。
结论1:设置快慢指针fast和slow,fast每次走两步,low每次走一步。假如有环,两者一定在环中相遇。(因为low指针一旦进环,可以看作是fast指针在追slow指针,因为fast指针每次走两步,slow指针每次走一步,所以最后一定能相遇)。
结论2:我们看上面的简化图,链表头a到链表环入口节点b的距离定义为l,环入口b到相遇点p的距离(右边)定义为m,相遇点p到环入口b的距离(左边)定义为n。
当快指针和慢指针相遇时:
快指针路程 = l+(m+n)k+m,k>=1,其中m+n为环的长度,k为环的圈数(k>=1,即最少一圈,不能是0圈,不然快慢指针走的路程一样,矛盾)。
慢指针路程 = l+m。
因为快指针的路程是慢指针的路程的两倍,所以:(l+m)*2 = l+(m+n)k+m,其中k>=1。
化简得到 l =(k-1)(m+n)+n
这个式子的意思是:链表头到环入口的距离=相遇点到环入口的距离+(k-1)圈数环长度。其中k>=1,所以k-1>=0圈。 所以两个指针分别从链表头和相遇点出发,最后一定相遇于环入口。
根据上面内容,可以写出判断是否为环链表的代码及找到环入口节点的代码。
1 | /** |
其实获取环链表入口节点返回null,也代表该链表不是环链表。
我们再来看下第二个问题,如何判断两个链表是否相交。
两个链表一般有这三种情况:两个无环链表、两个有环链表、一个有环链表和一个无环链表。
对于上面三种情况,我们分别来看下:
两个无环链表相交问题
两个无环链表A、B如果相交,则在相交点及之后的节点必然相同。如下图:
这非常容易理解,当A、B链表相交后,相交节点如果为PNode,则下一个节点 PNode.next 即是A的节点,也是B的节点。
因为从相交点往后两链表都是相同的,我们往前移动一定位置,较短的链表会到链表头。
因此我们以A、B当中较短的链表长度为准,从该位置遍历比较两个链表节点,如果节点相同,则说明A、B相交。
代码如下:
1 | /** |
两个有环链表相交问题
如果两个有环链表相交,则相交部分一定包含整个环。如下图:
一般有一个环入口节点和两个环入口节点两种情况。
因此我们可以先求两个环链表的入口节点,见上面代码。
- 如果入口节点是同一个的话,把相同的入口节点当作是尾节点,这个问题就退化成两个链表都无环,直接判断是否相交即可。
- 如果入口节点不是同一个的话,从第一个入口节点开始next下去,如果遇到第二个入口节点返回true即可;如果回到了本身的入口节点则表示没有相交,直接返回false。
相关代码如下:
1 | /** |
一个有环链表和一个无环链表相交问题
一个有环链表和一个无环链表是不可能相交的。
我们来简单分析下,如图:
我们假设有环链表A和无环链表B相交于环链表A非环部分的A点(虚线a表示),可以看到,对于非环链表B,当遍历到相交点时,还是可以继续next的,最后B也成为了环链表,这与B是非环链表矛盾。
假设它们相交于环链表A的环部分B点(虚线b表示),同理,对于非环链表B,当遍历到相交点时,还是可以继续next的,最后B也成为了环链表,这与B是非环链表矛盾。
这两种情况都是上面所述的两个环链表相交。
因此一个有环链表和一个无环链表是不可能相交的。
相交问题总结
根据上面的代码及分析,判断链表是否相交的代码如下:
1 | /** |
全部代码如下:
1 | public class LinkedList { |
总结
我们通过对链表的一些经典问题进行分析,加深了我们对于链表的一些理解。