单链表的相交以及有环无环问题（含数学证明）

浅浅的花香味﹌ 2023-07-19 10:43 24阅读 0赞

# 单链表的有无环判断以及数学证明 #

## 简介： ##

单链表判断有环无环，在数据结构考研和在笔试面试题中都是链表问题的重难点。下面从**拓扑关系**，**判断思路**，**数学证明**，**代码实现**四个方面来阐述。

## 拓扑关系 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70]  
单链表有环必定只有一个环，这是由单链表每个结点只有一个next指针来确定的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 1]  
上面的拓扑结构必然不可能给出现，因为结点3出现了两个next。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 2]  
另外值得注意的是两个结点之间也可以形成一个封闭的环。

## 判断思路 ##

如何才能用最低的时间复杂度和空间复杂度来找出环的入口呢？  
使用一个快指针和一个慢指针，这个技巧适用于很多较难的链表题。  
快指针和慢指针从头结点出发，慢指针一次走一步，快指针一次走两步。  
![从头结点出发][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 3]  
![快指针一次走两步，慢指针一次走一步][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 4]  
当没有环的时候，fast一定会抢先一步到达空指针，所以就可以判断无环。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 5]  
当有环的时候，快指针一定会先入环，慢指针后入环，在某一次循环中，二者会相遇（后面可以证明在何处相遇）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 6]  
相遇之后fast指针回到头结点处，然后每次和slow指针一样，**一次只走一步**，fast指针和slow指针同时向下出发，一定会在入环结点处相遇。  
WTF？为何会有如此神奇的结论？下面用一段简短的数学证明来解答大家的疑惑。

## 数学证明 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 7]  
我们假定环之前的长度为 L，环的长度为 R，结点内的数字表示的是结点的序号，并不是结点的数据值。

### step1 ###

当我们的slow指针向前走了 L 步，刚好到达入环结点的时候，slow处于序号为 L + 1的结点处。  
此时的fast指针指向的序号位置是 L + 1 + (L % R),%表示的是取余。  
我们可以思考一下，当slow指针和fast指针在环上某点位置相遇的时候，我们是不是可以确定 fast 一定比 slow多走了整数圈！！  
理解上面这点很重要，这是下面要继续的关键，至此请读者理解了再继续看下去。

### step2 ###

目前的情况是slow也已入环，假设走了 k 步，slow和fast相遇。

slow此时的序号位置为 **L + 1 + k % R**  
fast此时的序号位置为 **L + 1 + ( (L %R) + 2k) % R**

部分人看到上面的式子可能暗暗的骂了一句，这是个啥玩意啊？  
不急，我们一步一步来。

L %R这个式子是可以化简的， L 可以看成 **aR + c（a和c都为整数，a >= 0, c >= 0）**,例如11 % 5时， 11可以看成 2 \* 5 + 1，a = 2，c = 1； 1 % 5时 ，a = 0，c = 1；  
好了，我们用上面这个化简方法来处理我们的已知条件。

fast 比 slow 多走了整数圈，那么fast一共比slow多走了多少步呢？  
答案是 L + 2k - k （通过简单的思考就可以得到）。  
所以 （L +2k - k）% R = 0 => (L + k) % R = 0  
上面的式子可以推出 L +k = aR,因为必然是R的整数倍嘛。

然后设 L = bR + c , k = dR + e;

### step3 ###

总结一下我们得到的条件：

1.  slow此时的序号位置为 **L + 1 + k % R**
2.  fast此时的序号位置为 **L + 1 + ( (L %R) + 2k) % R**
3.  L +k = aR
4.  L = bR + c
5.  k = dR + e

首先 3, 4 ,5联立 L+k = (b +d)R + c +e = aR;  
推出 c + e必然是R的整数倍。  
现在要证明的问题是当fast与slow相遇时，我只需要把fast返回head结点，步长调整为1，那么fast和slow共同走L步必然在L +1的结点处相遇。  
利用条件一已知， 需要证明的式子是L + 1+ ( k % R + L) %R = L +1 => ( k % R + L) %R = 0  
条件5得到 k %R = e  
条件4得到 d + L = bR +c + e  
又因为我们知道 c + e 同样为R的整数倍，所以可以推出  
（K %R + L）%R = 0成立，所以我们需要证明的问题就解决了。

## 代码实现 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 8]  
代码为C语言实现，行间注释，体现了算法思想。

# 两个单链表的相交问题 #

假设我们有两条单链表**A**和**B**

## A，B都无环的情况 ##

### 拓扑关系 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 9]  
我们发现两条链表若相交必然是后半部分某一个结点开始，往后都相交。

### 代码思路 ###

遍历一下两个链表，获得他们的长度和尾指针。  
首先比较一下尾指针，如果不相同就不相交，如果相同，进入下一个判断。  
遍历长的链表，直到二者长度相等，只有这个时候才可能存在公共结点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 10]  
两条链表同时遍历，逐个结点比较直到找到相等的那个结点，把他返回。

### 代码实现 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 11]

## A有环B无环 ##

这种情况必不可能存在，读者可以自行画个图

## A，B均有环 ##

我们可以比较A，B的入环点是否相同，如果不相同，就是下面的拓扑关系。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 12]  
此时只需要让一个入环点绕环一圈，看是否可以发现另一个入环点，如果发现了那么这两个单链表必然是相交的

如果两个入环点是一样的，那么二者必然相交  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 13]

# 总结 #

以上就是单链表相交问题和有环无环问题的总结了，如果有不足的地方还请指正。  
码字不易，各位看官觉得有用的话点个赞鼓励一下。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70]: /images/20230528/777a0ea416754167ba3406fb0d8b07ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 1]: /images/20230528/ee44ba13ca214a9180e23c056c088d32.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 2]: /images/20230528/ca0d805775c44ca3a5df31130617d038.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 3]: /images/20230528/a70f3f7bf8704a67970e0079aab8dea9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 4]: /images/20230528/bdf9af7eeb024e48a747292dab154d9d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 5]: /images/20230528/303e8e2dc0ad4f8f8a526250961344bc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 6]: /images/20230528/fcc1372536984797854242d19062dd59.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 7]: /images/20230528/039d543f148f4fb29dcbb54458326118.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 8]: /images/20230528/1050cc1b8da14adf94de47f10485b132.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 9]: /images/20230528/2ec56829990f4be7b7927b9c84c9fb6c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 10]: /images/20230528/f69c4ce4d7eb4ba0ada02f949a3e5207.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 11]: /images/20230528/3b84caab0ded474684bd884e4c912d12.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 12]: /images/20230528/f84560d82baa4426ab4e4302e9829b8f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 13]: /images/20230528/afa087e9a807423ea4c56c5febdd595f.png